#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
const int MX = 1e5 + 5;
vector<pair<int, pii>> gr[MX];
int L[MX], R[MX], f[MX];
int ans[MX];
struct node{
int good, sum;
node(){
good = sum = 0;
}
};
struct SMT{
vector<node> tree;
int n = 1e5 + 5;
SMT(){
tree.assign(4*n + 5, node());
};
void update(int id, int l, int r, int u, int v, int val){
if(r < u || l > v){
return;
}
if(u <=l && r <= v){
tree[id].good += val;
tree[id].sum = (tree[id].good ? r-l+1 : tree[2*id].sum + tree[2*id+1].sum);
return;
}
int mid = (l + r) >> 1, ID = (id << 1);
update(ID, l, mid, u, v, val);
update(ID|1, mid+1, r, u, v, val);
tree[id].sum = (tree[id].good ? r-l+1 : tree[ID].sum + tree[ID|1].sum);
}
void update(int l, int r, int val){
update(1, 1, n, l, r, val);
}
int get(int id, int l, int r, int u, int v){
if(r < u || l > v){
return 0;
}
if(u <= l && r <= v){
return tree[id].sum;
}
int mid = (l + r) >> 1, ID = (id << 1);
return get(ID, l, mid, u, v) + get(ID|1, mid+1, r, u, v);
}
};
SMT smt;
void dfs(int u, int p){
ans[u] = smt.tree[1].sum;
for(pair<int, pii> e : gr[u]){
int v, l, r;
v = e.first;
tie(l, r) = e.second;
if(v != p){
smt.update(l, r, 1);
dfs(v, u);
smt.update(l, r, -1);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("main.inp","r",stdin);
//freopen("main.out","w",stdout);
int n, m;
cin>>n>>m;
for(int i=1; i<n; ++i){
int u, v, l, r;
cin>>u>>v>>l>>r;
gr[u].push_back({v, {l, r}});
gr[v].push_back({u, {l, r}});
}
dfs(1, 0);
for(int i=2; i<=n; ++i){
cout<<ans[i]<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10072 KB |
Output is correct |
2 |
Correct |
3 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10164 KB |
Output is correct |
4 |
Correct |
3 ms |
10072 KB |
Output is correct |
5 |
Correct |
3 ms |
10076 KB |
Output is correct |
6 |
Correct |
4 ms |
10116 KB |
Output is correct |
7 |
Correct |
3 ms |
9816 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
3 ms |
10076 KB |
Output is correct |
10 |
Correct |
3 ms |
10076 KB |
Output is correct |
11 |
Correct |
3 ms |
10076 KB |
Output is correct |
12 |
Correct |
3 ms |
10076 KB |
Output is correct |
13 |
Correct |
3 ms |
10076 KB |
Output is correct |
14 |
Correct |
4 ms |
10076 KB |
Output is correct |
15 |
Correct |
4 ms |
9820 KB |
Output is correct |
16 |
Correct |
3 ms |
9820 KB |
Output is correct |
17 |
Correct |
4 ms |
10076 KB |
Output is correct |
18 |
Correct |
3 ms |
10076 KB |
Output is correct |
19 |
Correct |
4 ms |
10076 KB |
Output is correct |
20 |
Correct |
4 ms |
9864 KB |
Output is correct |
21 |
Correct |
4 ms |
10076 KB |
Output is correct |
22 |
Correct |
3 ms |
10076 KB |
Output is correct |
23 |
Correct |
3 ms |
9820 KB |
Output is correct |
24 |
Correct |
3 ms |
9820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10072 KB |
Output is correct |
2 |
Correct |
3 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10164 KB |
Output is correct |
4 |
Correct |
3 ms |
10072 KB |
Output is correct |
5 |
Correct |
3 ms |
10076 KB |
Output is correct |
6 |
Correct |
4 ms |
10116 KB |
Output is correct |
7 |
Correct |
3 ms |
9816 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
3 ms |
10076 KB |
Output is correct |
10 |
Correct |
3 ms |
10076 KB |
Output is correct |
11 |
Correct |
3 ms |
10076 KB |
Output is correct |
12 |
Correct |
3 ms |
10076 KB |
Output is correct |
13 |
Correct |
3 ms |
10076 KB |
Output is correct |
14 |
Correct |
4 ms |
10076 KB |
Output is correct |
15 |
Correct |
4 ms |
9820 KB |
Output is correct |
16 |
Correct |
3 ms |
9820 KB |
Output is correct |
17 |
Correct |
4 ms |
10076 KB |
Output is correct |
18 |
Correct |
3 ms |
10076 KB |
Output is correct |
19 |
Correct |
4 ms |
10076 KB |
Output is correct |
20 |
Correct |
4 ms |
9864 KB |
Output is correct |
21 |
Correct |
4 ms |
10076 KB |
Output is correct |
22 |
Correct |
3 ms |
10076 KB |
Output is correct |
23 |
Correct |
3 ms |
9820 KB |
Output is correct |
24 |
Correct |
3 ms |
9820 KB |
Output is correct |
25 |
Incorrect |
3 ms |
10076 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10072 KB |
Output is correct |
2 |
Correct |
3 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10164 KB |
Output is correct |
4 |
Correct |
3 ms |
10072 KB |
Output is correct |
5 |
Correct |
3 ms |
10076 KB |
Output is correct |
6 |
Correct |
4 ms |
10116 KB |
Output is correct |
7 |
Correct |
3 ms |
9816 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
3 ms |
10076 KB |
Output is correct |
10 |
Correct |
3 ms |
10076 KB |
Output is correct |
11 |
Correct |
3 ms |
10076 KB |
Output is correct |
12 |
Correct |
3 ms |
10076 KB |
Output is correct |
13 |
Correct |
3 ms |
10076 KB |
Output is correct |
14 |
Correct |
4 ms |
10076 KB |
Output is correct |
15 |
Correct |
4 ms |
9820 KB |
Output is correct |
16 |
Correct |
3 ms |
9820 KB |
Output is correct |
17 |
Correct |
4 ms |
10076 KB |
Output is correct |
18 |
Correct |
3 ms |
10076 KB |
Output is correct |
19 |
Correct |
4 ms |
10076 KB |
Output is correct |
20 |
Correct |
4 ms |
9864 KB |
Output is correct |
21 |
Correct |
4 ms |
10076 KB |
Output is correct |
22 |
Correct |
3 ms |
10076 KB |
Output is correct |
23 |
Correct |
3 ms |
9820 KB |
Output is correct |
24 |
Correct |
3 ms |
9820 KB |
Output is correct |
25 |
Correct |
35 ms |
21272 KB |
Output is correct |
26 |
Correct |
35 ms |
21188 KB |
Output is correct |
27 |
Correct |
50 ms |
21112 KB |
Output is correct |
28 |
Correct |
45 ms |
21332 KB |
Output is correct |
29 |
Correct |
34 ms |
21188 KB |
Output is correct |
30 |
Correct |
34 ms |
21160 KB |
Output is correct |
31 |
Correct |
6 ms |
11096 KB |
Output is correct |
32 |
Correct |
6 ms |
11100 KB |
Output is correct |
33 |
Correct |
6 ms |
11160 KB |
Output is correct |
34 |
Correct |
8 ms |
11180 KB |
Output is correct |
35 |
Correct |
34 ms |
16280 KB |
Output is correct |
36 |
Correct |
42 ms |
16672 KB |
Output is correct |
37 |
Correct |
45 ms |
16220 KB |
Output is correct |
38 |
Correct |
46 ms |
16464 KB |
Output is correct |
39 |
Correct |
32 ms |
16208 KB |
Output is correct |
40 |
Correct |
42 ms |
16208 KB |
Output is correct |
41 |
Correct |
8 ms |
10556 KB |
Output is correct |
42 |
Correct |
7 ms |
10332 KB |
Output is correct |
43 |
Correct |
36 ms |
15676 KB |
Output is correct |
44 |
Correct |
36 ms |
15708 KB |
Output is correct |
45 |
Correct |
48 ms |
15808 KB |
Output is correct |
46 |
Correct |
47 ms |
15580 KB |
Output is correct |
47 |
Correct |
37 ms |
15708 KB |
Output is correct |
48 |
Correct |
34 ms |
15448 KB |
Output is correct |
49 |
Correct |
6 ms |
10332 KB |
Output is correct |
50 |
Correct |
7 ms |
10332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10072 KB |
Output is correct |
2 |
Correct |
3 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10164 KB |
Output is correct |
4 |
Correct |
3 ms |
10072 KB |
Output is correct |
5 |
Correct |
3 ms |
10076 KB |
Output is correct |
6 |
Correct |
4 ms |
10116 KB |
Output is correct |
7 |
Correct |
3 ms |
9816 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
3 ms |
10076 KB |
Output is correct |
10 |
Correct |
3 ms |
10076 KB |
Output is correct |
11 |
Correct |
3 ms |
10076 KB |
Output is correct |
12 |
Correct |
3 ms |
10076 KB |
Output is correct |
13 |
Correct |
3 ms |
10076 KB |
Output is correct |
14 |
Correct |
4 ms |
10076 KB |
Output is correct |
15 |
Correct |
4 ms |
9820 KB |
Output is correct |
16 |
Correct |
3 ms |
9820 KB |
Output is correct |
17 |
Correct |
4 ms |
10076 KB |
Output is correct |
18 |
Correct |
3 ms |
10076 KB |
Output is correct |
19 |
Correct |
4 ms |
10076 KB |
Output is correct |
20 |
Correct |
4 ms |
9864 KB |
Output is correct |
21 |
Correct |
4 ms |
10076 KB |
Output is correct |
22 |
Correct |
3 ms |
10076 KB |
Output is correct |
23 |
Correct |
3 ms |
9820 KB |
Output is correct |
24 |
Correct |
3 ms |
9820 KB |
Output is correct |
25 |
Correct |
35 ms |
21272 KB |
Output is correct |
26 |
Correct |
35 ms |
21188 KB |
Output is correct |
27 |
Correct |
50 ms |
21112 KB |
Output is correct |
28 |
Correct |
45 ms |
21332 KB |
Output is correct |
29 |
Correct |
34 ms |
21188 KB |
Output is correct |
30 |
Correct |
34 ms |
21160 KB |
Output is correct |
31 |
Correct |
6 ms |
11096 KB |
Output is correct |
32 |
Correct |
6 ms |
11100 KB |
Output is correct |
33 |
Correct |
6 ms |
11160 KB |
Output is correct |
34 |
Correct |
8 ms |
11180 KB |
Output is correct |
35 |
Correct |
34 ms |
16280 KB |
Output is correct |
36 |
Correct |
42 ms |
16672 KB |
Output is correct |
37 |
Correct |
45 ms |
16220 KB |
Output is correct |
38 |
Correct |
46 ms |
16464 KB |
Output is correct |
39 |
Correct |
32 ms |
16208 KB |
Output is correct |
40 |
Correct |
42 ms |
16208 KB |
Output is correct |
41 |
Correct |
8 ms |
10556 KB |
Output is correct |
42 |
Correct |
7 ms |
10332 KB |
Output is correct |
43 |
Correct |
36 ms |
15676 KB |
Output is correct |
44 |
Correct |
36 ms |
15708 KB |
Output is correct |
45 |
Correct |
48 ms |
15808 KB |
Output is correct |
46 |
Correct |
47 ms |
15580 KB |
Output is correct |
47 |
Correct |
37 ms |
15708 KB |
Output is correct |
48 |
Correct |
34 ms |
15448 KB |
Output is correct |
49 |
Correct |
6 ms |
10332 KB |
Output is correct |
50 |
Correct |
7 ms |
10332 KB |
Output is correct |
51 |
Runtime error |
104 ms |
66840 KB |
Execution killed with signal 11 |
52 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10072 KB |
Output is correct |
2 |
Correct |
3 ms |
10076 KB |
Output is correct |
3 |
Correct |
4 ms |
10164 KB |
Output is correct |
4 |
Correct |
3 ms |
10072 KB |
Output is correct |
5 |
Correct |
3 ms |
10076 KB |
Output is correct |
6 |
Correct |
4 ms |
10116 KB |
Output is correct |
7 |
Correct |
3 ms |
9816 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
3 ms |
10076 KB |
Output is correct |
10 |
Correct |
3 ms |
10076 KB |
Output is correct |
11 |
Correct |
3 ms |
10076 KB |
Output is correct |
12 |
Correct |
3 ms |
10076 KB |
Output is correct |
13 |
Correct |
3 ms |
10076 KB |
Output is correct |
14 |
Correct |
4 ms |
10076 KB |
Output is correct |
15 |
Correct |
4 ms |
9820 KB |
Output is correct |
16 |
Correct |
3 ms |
9820 KB |
Output is correct |
17 |
Correct |
4 ms |
10076 KB |
Output is correct |
18 |
Correct |
3 ms |
10076 KB |
Output is correct |
19 |
Correct |
4 ms |
10076 KB |
Output is correct |
20 |
Correct |
4 ms |
9864 KB |
Output is correct |
21 |
Correct |
4 ms |
10076 KB |
Output is correct |
22 |
Correct |
3 ms |
10076 KB |
Output is correct |
23 |
Correct |
3 ms |
9820 KB |
Output is correct |
24 |
Correct |
3 ms |
9820 KB |
Output is correct |
25 |
Incorrect |
3 ms |
10076 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |