#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int SQ = 100;
int N, M, Q;
vector<int> adj[MAXN+10];
int A[MAXN+10];
struct Data
{
int l, r, k;
};
Data B[MAXN+10];
multiset<pii> S;
int dfn[MAXN+10], cnt, par[MAXN+10][30], dep[MAXN+10];
void dfs(int now, int bef, int d)
{
dfn[now]=++cnt;
dep[now]=d;
par[now][0]=bef;
for(auto nxt : adj[now])
{
if(nxt==bef) continue;
dfs(nxt, now, d+1);
}
}
int lca(int u, int v)
{
if(dep[u]>dep[v]) swap(u, v);
for(int i=20; i>=0; i--) if(dep[u]<=dep[par[v][i]]) v=par[v][i];
if(u==v) return u;
for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
return par[u][0];
}
int dist(int u, int v)
{
return dep[u]+dep[v]-dep[lca(u, v)]*2;
}
int ans=0, ans1[MAXN+10];
void push(int x)
{
auto it=S.lower_bound({dfn[x], x});
set<pii>::iterator lt, rt;
if(it==S.end()) lt=prev(it), rt=S.begin();
else if(it==S.begin()) rt=it, lt=prev(S.end());
else rt=it, lt=prev(it);
S.insert({dfn[x], x});
ans-=dist(rt->second, lt->second);
ans+=dist(rt->second, x);
ans+=dist(lt->second, x);
//printf("PUSH %d %d\n", x, ans);
}
void pop(int x)
{
auto it=S.lower_bound({dfn[x], x});
set<pii>::iterator lt, rt;
if(it==S.begin()) lt=prev(S.end());
else lt=prev(it);
if(it==prev(S.end())) rt=S.begin();
else rt=next(it);
S.erase(S.find({dfn[x], x}));
ans+=dist(rt->second, lt->second);
ans-=dist(rt->second, x);
ans-=dist(lt->second, x);
//printf("POP %d %d\n", x, ans);
}
int main()
{
scanf("%d%d%d", &N, &M, &Q);
for(int i=1; i<N; i++)
{
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1; i<=M; i++) scanf("%d", &A[i]);
for(int i=1; i<=Q; i++) scanf("%d%d", &B[i].l, &B[i].r), B[i].k=i;
sort(B+1, B+Q+1, [&](const Data &p, const Data &q)
{
if(p.l/SQ==q.l/SQ) return p.r<q.r;
return p.l/SQ<q.l/SQ;
});
dfs(1, 1, 1);
for(int j=1; j<=20; j++) for(int i=1; i<=N; i++) par[i][j]=par[par[i][j-1]][j-1];
int l=1, r=1;
S.insert({dfn[A[1]], A[1]});
for(int i=1; i<=Q; i++)
{
while(r<B[i].r) push(A[++r]);
while(B[i].l<l) push(A[--l]);
while(r>B[i].r) pop(A[r--]);
while(l<B[i].l) pop(A[l++]);
ans1[B[i].k]=ans/2;
}
for(int i=1; i<=Q; i++) printf("%d\n", ans1[i]+1);
}
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d%d%d", &N, &M, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
tourism.cpp:91:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | for(int i=1; i<=M; i++) scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
tourism.cpp:92:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | for(int i=1; i<=Q; i++) scanf("%d%d", &B[i].l, &B[i].r), B[i].k=i;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
6 ms |
2644 KB |
Output is correct |
5 |
Correct |
5 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
2716 KB |
Output is correct |
7 |
Correct |
7 ms |
2644 KB |
Output is correct |
8 |
Correct |
5 ms |
2644 KB |
Output is correct |
9 |
Correct |
8 ms |
2644 KB |
Output is correct |
10 |
Correct |
8 ms |
2644 KB |
Output is correct |
11 |
Correct |
8 ms |
2644 KB |
Output is correct |
12 |
Correct |
3 ms |
2676 KB |
Output is correct |
13 |
Correct |
3 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2644 KB |
Output is correct |
15 |
Correct |
7 ms |
2644 KB |
Output is correct |
16 |
Correct |
5 ms |
2644 KB |
Output is correct |
17 |
Correct |
6 ms |
2644 KB |
Output is correct |
18 |
Correct |
7 ms |
2644 KB |
Output is correct |
19 |
Correct |
8 ms |
2644 KB |
Output is correct |
20 |
Correct |
9 ms |
2732 KB |
Output is correct |
21 |
Correct |
8 ms |
2644 KB |
Output is correct |
22 |
Correct |
8 ms |
2644 KB |
Output is correct |
23 |
Correct |
8 ms |
2644 KB |
Output is correct |
24 |
Correct |
8 ms |
2644 KB |
Output is correct |
25 |
Correct |
8 ms |
2744 KB |
Output is correct |
26 |
Correct |
8 ms |
2644 KB |
Output is correct |
27 |
Correct |
5 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
6 ms |
2644 KB |
Output is correct |
5 |
Correct |
5 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
2716 KB |
Output is correct |
7 |
Correct |
7 ms |
2644 KB |
Output is correct |
8 |
Correct |
5 ms |
2644 KB |
Output is correct |
9 |
Correct |
8 ms |
2644 KB |
Output is correct |
10 |
Correct |
8 ms |
2644 KB |
Output is correct |
11 |
Correct |
8 ms |
2644 KB |
Output is correct |
12 |
Correct |
3 ms |
2676 KB |
Output is correct |
13 |
Correct |
3 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2644 KB |
Output is correct |
15 |
Correct |
7 ms |
2644 KB |
Output is correct |
16 |
Correct |
5 ms |
2644 KB |
Output is correct |
17 |
Correct |
6 ms |
2644 KB |
Output is correct |
18 |
Correct |
7 ms |
2644 KB |
Output is correct |
19 |
Correct |
8 ms |
2644 KB |
Output is correct |
20 |
Correct |
9 ms |
2732 KB |
Output is correct |
21 |
Correct |
8 ms |
2644 KB |
Output is correct |
22 |
Correct |
8 ms |
2644 KB |
Output is correct |
23 |
Correct |
8 ms |
2644 KB |
Output is correct |
24 |
Correct |
8 ms |
2644 KB |
Output is correct |
25 |
Correct |
8 ms |
2744 KB |
Output is correct |
26 |
Correct |
8 ms |
2644 KB |
Output is correct |
27 |
Correct |
5 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
66 ms |
2980 KB |
Output is correct |
31 |
Correct |
83 ms |
2992 KB |
Output is correct |
32 |
Correct |
77 ms |
3108 KB |
Output is correct |
33 |
Correct |
72 ms |
3104 KB |
Output is correct |
34 |
Correct |
76 ms |
3108 KB |
Output is correct |
35 |
Correct |
19 ms |
3128 KB |
Output is correct |
36 |
Correct |
21 ms |
3124 KB |
Output is correct |
37 |
Correct |
29 ms |
3116 KB |
Output is correct |
38 |
Correct |
54 ms |
3136 KB |
Output is correct |
39 |
Correct |
54 ms |
3176 KB |
Output is correct |
40 |
Correct |
63 ms |
3156 KB |
Output is correct |
41 |
Correct |
18 ms |
3200 KB |
Output is correct |
42 |
Correct |
16 ms |
3156 KB |
Output is correct |
43 |
Correct |
16 ms |
3156 KB |
Output is correct |
44 |
Correct |
57 ms |
3156 KB |
Output is correct |
45 |
Correct |
56 ms |
3148 KB |
Output is correct |
46 |
Correct |
56 ms |
3136 KB |
Output is correct |
47 |
Correct |
21 ms |
3028 KB |
Output is correct |
48 |
Correct |
16 ms |
3132 KB |
Output is correct |
49 |
Correct |
19 ms |
3156 KB |
Output is correct |
50 |
Correct |
78 ms |
3028 KB |
Output is correct |
51 |
Correct |
78 ms |
3112 KB |
Output is correct |
52 |
Correct |
80 ms |
3108 KB |
Output is correct |
53 |
Correct |
105 ms |
3136 KB |
Output is correct |
54 |
Correct |
82 ms |
3028 KB |
Output is correct |
55 |
Correct |
74 ms |
3072 KB |
Output is correct |
56 |
Correct |
61 ms |
2772 KB |
Output is correct |
57 |
Correct |
3 ms |
2900 KB |
Output is correct |
58 |
Correct |
6 ms |
3028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
6 ms |
2692 KB |
Output is correct |
3 |
Correct |
45 ms |
2772 KB |
Output is correct |
4 |
Execution timed out |
5029 ms |
19632 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
124 ms |
11464 KB |
Output is correct |
3 |
Correct |
186 ms |
12412 KB |
Output is correct |
4 |
Correct |
156 ms |
13608 KB |
Output is correct |
5 |
Correct |
211 ms |
23596 KB |
Output is correct |
6 |
Correct |
303 ms |
21872 KB |
Output is correct |
7 |
Correct |
317 ms |
19816 KB |
Output is correct |
8 |
Correct |
304 ms |
19124 KB |
Output is correct |
9 |
Correct |
280 ms |
18796 KB |
Output is correct |
10 |
Correct |
293 ms |
18936 KB |
Output is correct |
11 |
Correct |
258 ms |
18804 KB |
Output is correct |
12 |
Correct |
248 ms |
18844 KB |
Output is correct |
13 |
Correct |
232 ms |
18868 KB |
Output is correct |
14 |
Correct |
235 ms |
19368 KB |
Output is correct |
15 |
Correct |
209 ms |
20500 KB |
Output is correct |
16 |
Correct |
287 ms |
21068 KB |
Output is correct |
17 |
Correct |
263 ms |
21068 KB |
Output is correct |
18 |
Correct |
280 ms |
21036 KB |
Output is correct |
19 |
Correct |
185 ms |
23432 KB |
Output is correct |
20 |
Correct |
247 ms |
23388 KB |
Output is correct |
21 |
Correct |
288 ms |
20736 KB |
Output is correct |
22 |
Correct |
293 ms |
19660 KB |
Output is correct |
23 |
Correct |
319 ms |
19324 KB |
Output is correct |
24 |
Correct |
311 ms |
18876 KB |
Output is correct |
25 |
Correct |
312 ms |
18800 KB |
Output is correct |
26 |
Correct |
366 ms |
18984 KB |
Output is correct |
27 |
Correct |
371 ms |
18812 KB |
Output is correct |
28 |
Correct |
380 ms |
18836 KB |
Output is correct |
29 |
Correct |
348 ms |
18704 KB |
Output is correct |
30 |
Correct |
353 ms |
18856 KB |
Output is correct |
31 |
Correct |
352 ms |
18892 KB |
Output is correct |
32 |
Correct |
337 ms |
19068 KB |
Output is correct |
33 |
Correct |
329 ms |
19628 KB |
Output is correct |
34 |
Correct |
246 ms |
20796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
5 ms |
2700 KB |
Output is correct |
3 |
Correct |
42 ms |
2772 KB |
Output is correct |
4 |
Execution timed out |
5051 ms |
17408 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
6 ms |
2644 KB |
Output is correct |
5 |
Correct |
5 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
2716 KB |
Output is correct |
7 |
Correct |
7 ms |
2644 KB |
Output is correct |
8 |
Correct |
5 ms |
2644 KB |
Output is correct |
9 |
Correct |
8 ms |
2644 KB |
Output is correct |
10 |
Correct |
8 ms |
2644 KB |
Output is correct |
11 |
Correct |
8 ms |
2644 KB |
Output is correct |
12 |
Correct |
3 ms |
2676 KB |
Output is correct |
13 |
Correct |
3 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2644 KB |
Output is correct |
15 |
Correct |
7 ms |
2644 KB |
Output is correct |
16 |
Correct |
5 ms |
2644 KB |
Output is correct |
17 |
Correct |
6 ms |
2644 KB |
Output is correct |
18 |
Correct |
7 ms |
2644 KB |
Output is correct |
19 |
Correct |
8 ms |
2644 KB |
Output is correct |
20 |
Correct |
9 ms |
2732 KB |
Output is correct |
21 |
Correct |
8 ms |
2644 KB |
Output is correct |
22 |
Correct |
8 ms |
2644 KB |
Output is correct |
23 |
Correct |
8 ms |
2644 KB |
Output is correct |
24 |
Correct |
8 ms |
2644 KB |
Output is correct |
25 |
Correct |
8 ms |
2744 KB |
Output is correct |
26 |
Correct |
8 ms |
2644 KB |
Output is correct |
27 |
Correct |
5 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
66 ms |
2980 KB |
Output is correct |
31 |
Correct |
83 ms |
2992 KB |
Output is correct |
32 |
Correct |
77 ms |
3108 KB |
Output is correct |
33 |
Correct |
72 ms |
3104 KB |
Output is correct |
34 |
Correct |
76 ms |
3108 KB |
Output is correct |
35 |
Correct |
19 ms |
3128 KB |
Output is correct |
36 |
Correct |
21 ms |
3124 KB |
Output is correct |
37 |
Correct |
29 ms |
3116 KB |
Output is correct |
38 |
Correct |
54 ms |
3136 KB |
Output is correct |
39 |
Correct |
54 ms |
3176 KB |
Output is correct |
40 |
Correct |
63 ms |
3156 KB |
Output is correct |
41 |
Correct |
18 ms |
3200 KB |
Output is correct |
42 |
Correct |
16 ms |
3156 KB |
Output is correct |
43 |
Correct |
16 ms |
3156 KB |
Output is correct |
44 |
Correct |
57 ms |
3156 KB |
Output is correct |
45 |
Correct |
56 ms |
3148 KB |
Output is correct |
46 |
Correct |
56 ms |
3136 KB |
Output is correct |
47 |
Correct |
21 ms |
3028 KB |
Output is correct |
48 |
Correct |
16 ms |
3132 KB |
Output is correct |
49 |
Correct |
19 ms |
3156 KB |
Output is correct |
50 |
Correct |
78 ms |
3028 KB |
Output is correct |
51 |
Correct |
78 ms |
3112 KB |
Output is correct |
52 |
Correct |
80 ms |
3108 KB |
Output is correct |
53 |
Correct |
105 ms |
3136 KB |
Output is correct |
54 |
Correct |
82 ms |
3028 KB |
Output is correct |
55 |
Correct |
74 ms |
3072 KB |
Output is correct |
56 |
Correct |
61 ms |
2772 KB |
Output is correct |
57 |
Correct |
3 ms |
2900 KB |
Output is correct |
58 |
Correct |
6 ms |
3028 KB |
Output is correct |
59 |
Correct |
2 ms |
2644 KB |
Output is correct |
60 |
Correct |
6 ms |
2692 KB |
Output is correct |
61 |
Correct |
45 ms |
2772 KB |
Output is correct |
62 |
Execution timed out |
5029 ms |
19632 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |