QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#626445#5403. 树数术Flamire10 963ms261908kbC++172.6kb2024-10-10 09:05:192024-10-10 09:05:20

Judging History

你现在查看的是最新测评结果

  • [2024-10-10 09:05:20]
  • 评测
  • 测评结果:10
  • 用时:963ms
  • 内存:261908kb
  • [2024-10-10 09:05:19]
  • 提交

answer

#include <bits/stdc++.h>
#define N 700011
#define pii pair<int,int>
#define s1 first
#define s2 second
#define ll long long
using namespace std;
int n,m,q,a[N];
vector<int> G[N];int dfn[N],siz[N],dep[N],h[N],st[21][N],rk[N],clk,lg[N];
void dfs(int u,int F)
{
	dfn[u]=++clk;dep[u]=dep[F]+1;rk[clk]=u;h[clk]=u;siz[u]=1;
	for(int v:G[u])if(v^F)
	{
		dfs(v,u);
		h[clk]=u;siz[u]+=siz[v];
	}
}
int lca(int x,int y)
{
	if(x==y)return x;
	if(rk[x]>rk[y])swap(x,y);
	int logl=lg[rk[y]-rk[x]];
	int u1=st[logl][rk[x]],u2=st[logl][rk[y]-(1<<logl)];
	return dep[u1]<dep[u2]?u1:u2;
}
int rg[21][N];
int qlca(int l,int r)
{
	if(l==r)return l;
	int logl=lg[r-l];
	int u1=rg[logl][l],u2=rg[logl][r-(1<<logl)];
	return lca(u1,u2);
}
struct kueri{int x,y,k,id;};
vector<kueri> vk[N];
vector<pii> vv;
int ql[N],qr[N];
ll ans[N];
bool insub(int u,int v){return dfn[u]<=dfn[v]&&dfn[v]<dfn[u]+siz[u];}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}
	dfs(1,0);
	for(int i=1;i<n;++i)st[0][i]=h[i];
	for(int i=1;i<=20;++i)
	{
		for(int j=1;j+(1<<i)-1<n;++j)
		{
			int u1=st[i-1][j],u2=st[i-1][j+(1<<i-1)];
			st[i][j]=dep[u1]<dep[u2]?u1:u2;
		}
	}
	lg[0]=-1;for(int i=1;i<N;++i)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=m;++i)scanf("%d",a+i);
	for(int i=1;i<m;++i)rg[0][i]=lca(a[i],a[i+1]);
	for(int i=1;i<=20;++i)
	{
		for(int j=1;j+(1<<i)-1<m;++j)
		{
			int u1=rg[i-1][j],u2=rg[i-1][j+(1<<i-1)];
			rg[i][j]=lca(u1,u2);
		}
	}
	for(int i=1;i<=q;++i)
	{
		int k;scanf("%d",&k);
		for(int j=1;j<=k;++j)scanf("%d%d",ql+j,qr+j);
		int x=-1;
		for(int j=1;j<=k;++j)
		{
			vk[ql[j]].push_back({ql[j],qr[j],x,i});
			// printf("([%d,%d],x:%d) ",ql[j],qr[j],x);
			if(~x)x=lca(x,qlca(ql[j],qr[j]));
			else x=qlca(ql[j],qr[j]);
		}
		// putchar(10);
	}
	for(int i=m;i;--i)
	{
		int x=a[i];
		while(!vv.empty()&&!insub(vv.back().s1,a[i]))x=lca(vv.back().s1,a[i]),vv.pop_back();
		vv.push_back({x,i});
		// printf("i:%d vv:",i);for(pii x:vv)printf("{%d,%d} ",x.s1,x.s2);putchar(10);
		for(kueri k:vk[i])
		{
			int L=0,R=(int)vv.size()-1,rb=-1;
			if(~k.k)
			{
				while(L<=R)
				{
					int M=L+R>>1;
					if(insub(vv[M].s1,k.k))rb=M,L=M+1;else R=M-1;
				}
			}
			else rb=(int)vv.size()-1;
			L=0,R=(int)vv.size()-1;int lb=vv.size();
			while(L<=R)
			{
				int M=L+R>>1;
				if(vv[M].s2<=k.y)lb=M,R=M-1;else L=M+1;
			}
			// printf("query([%d,%d],x:%d) lb:%d rb:%d\n",k.x,k.y,k.k,lb,rb);
			ans[k.id]+=max(0,rb-lb+1);
		}
	}
	for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
	fclose(stdin);fclose(stdout);return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 963ms
memory: 261908kb

input:

699990 699995 233333
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

121987
139520
87432
42773
311773
194269
177810
454211
417130
299450
366103
227736
186417
163975
292497
216139
401719
16634
192685
27351
52127
54938
142169
275076
339876
117003
51132
229206
187647
350043
398455
83905
100490
338070
356664
60211
366172
142627
16903
222331
471095
184145
170758
238393
14...

result:

ok 233333 lines

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 686ms
memory: 234676kb

input:

699992 699994 699992
2 1
3 1
4 3
5 3
6 5
7 5
8 7
9 7
10 9
11 9
12 11
13 11
14 13
15 13
16 15
17 15
18 17
19 17
20 19
21 19
22 21
23 21
24 23
25 23
26 25
27 25
28 27
29 27
30 29
31 29
32 31
33 31
34 33
35 33
36 35
37 35
38 37
39 37
40 39
41 39
42 41
43 40
44 43
45 43
46 45
47 45
48 47
49 47
50 49
51 ...

output:

40532
1
1
1
1
19424
1
1
7685
13612
34566
1
1
4584
1
1
1
1
20904
1
1
12638
1
22842
1
1
1
1
1
1
17435
1
1
1
1
1
1
1
1
1
1
8104
1
17860
1
1
1
5332
1
1
1
1
1
1
23026
1
1
1
1
1
16008
1
1
1
1
1
1
1
1
1
1
5114
23529
1
8158
1
1
1
1
1
1
1
1
1
1
1
4685
1
13376
1
1
3637
29719
1
1
1
1
1
1
1
1
1
1
1
1
1
1
16213
...

result:

wrong answer 1st lines differ - expected: '211594', found: '40532'

Subtask #3:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 63ms
memory: 141440kb

input:

99998 99993 33333
2 1
3 1
4 3
5 3
6 5
7 5
8 7
9 7
10 9
11 9
12 11
13 11
14 13
15 13
16 15
17 15
18 17
19 17
20 19
21 19
22 21
23 21
24 23
25 23
26 25
27 25
28 27
29 27
30 29
31 24
32 31
33 31
34 33
35 33
36 35
37 35
38 37
39 37
40 39
41 39
42 41
43 41
44 43
45 43
46 45
47 45
48 47
49 47
50 49
51 49
...

output:

1
2
1
3245
2274
4571
75
2314
5788
1372
5849
1
1
3849
410
1260
125
554
1322
175
1
1456
1970
1741
1
382
715
1592
1
1
707
1
3009
1
1
1
1
2
5510
1682
2511
350
1
1251
1
1
2118
1
1110
3397
101
247
5179
3118
372
1
2304
1
1
1826
1496
912
473
1
889
1
558
1212
1
2576
1
13
1
196
5766
1757
1
2350
1
1
3623
1
501...

result:

wrong answer 1st lines differ - expected: '9733', found: '1'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%