QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#626462#5403. 树数术Flamire30 841ms267060kbC++172.7kb2024-10-10 09:20:072024-10-10 09:20:08

Judging History

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

  • [2024-10-10 09:20:08]
  • 评测
  • 测评结果:30
  • 用时:841ms
  • 内存:267060kb
  • [2024-10-10 09:20:07]
  • 提交

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 a[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];
struct point{int x,id,w;};
vector<point> vv;
int sum[N];
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];}
void push(point p)
{
	vv.push_back(p);
	sum[vv.size()-1]=(vv.size()>=2?sum[vv.size()-2]:0)+p.w;
}
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().x,a[i]))vv.pop_back();
		push({x,i,1});
		// printf("i:%d vv:",i);for(point x:vv)printf("{%d,%d,%d} ",x.x,x.id,x.w);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].x,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].id<=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,sum[rb]-(lb>0?sum[lb-1]:0));
		}
	}
	for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
	fclose(stdin);fclose(stdout);return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 841ms
memory: 267060kb

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: 20
Accepted

Test #2:

score: 20
Accepted
time: 764ms
memory: 241864kb

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:

211594
160846
176729
128251
32662
70710
74884
9095
68282
91324
154262
24279
31878
173468
75265
139715
91660
87525
194302
16875
81535
172911
29145
20483
151883
5255
9548
58890
38076
94152
14358
74859
48870
23981
41390
60976
13795
125823
427
26641
130620
174231
73241
55291
2364
78864
23391
4866
36002
...

result:

ok 699992 lines

Subtask #3:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 87ms
memory: 158828kb

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:

5288
11330
2539
2383
5320
21087
1080
8240
8100
834
8917
11977
6312
6132
2427
820
87
18283
792
139
21383
8288
8903
5714
15707
264
533
3283
13883
3828
645
16796
1995
6434
8490
20419
3448
12192
11300
1003
1768
269
4114
743
7340
4485
14902
8747
817
11878
12023
146
7704
3173
268
15606
10316
3008
3540
110...

result:

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

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%