QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417106#8716. 树FlyingFeatherAC ✓1153ms33536kbC++173.0kb2024-05-22 14:25:462024-05-22 14:26:36

Judging History

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

  • [2024-05-22 14:26:36]
  • 评测
  • 测评结果:AC
  • 用时:1153ms
  • 内存:33536kb
  • [2024-05-22 14:25:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>v[N];
int a[N],b[N],depth[N],fa[N][20];
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0] = 0,depth[root] = 1;
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(auto j:v[t])
        {
            if(depth[j]>depth[t]+1)
            {
                depth[j] = depth[t]+1;
                q.push(j);
                fa[j][0] = t;
                for(int k=1;k<=19;k++)
                {
                    fa[j][k] = fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
}
int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 19; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 19; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}
int cal(int i)
{
	if(b[i]==0)
	{
		if(b[i+1]==0)  return 0;
		else if(b[i+1]==1)  return 1;
		else  return 1;
	}
	else if(b[i]==1)
	{
		if(b[i+1]==0)
		{
			if(lca(a[i],a[i+2])==a[i]||lca(a[i],a[i+2])==a[i+2])  return 1;
			else
			{
				if(lca(a[i],a[i+2])==a[i+1])  return 0;
				return 1;
			}
		}
		else if(b[i+1]==1)  return 0;
		else  return 0;
	}
	else
	{
		if(b[i+1]==0)  return 0;
		else if(b[i+1]==1)  return 1;
		else  return 1;
	}
}
int main()
{
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		v[x].push_back(y),v[y].push_back(x);
	}
	bfs(1);
	for(int i=1;i<=m;i++)  cin>>a[i];
	for(int i=1;i<m;i++)
	{
		if(lca(a[i],a[i+1])==a[i])  b[i]=0;
		else if(lca(a[i],a[i+1])==a[i+1])  b[i]=1;
		else  b[i]=2;
	}
	if(m<=2)
	{
		for(int i=1;i<=q;i++)  cout<<m<<endl;
		return 0;
	}
	int ans=2;
	//for(int i=1;i<m;i++)  cout<<b[i]<<" ";
	//cout<<endl;
	for(int i=1;i<m-1;i++)  ans+=cal(i);
	//cout<<ans<<endl;
	while(q--)
	{
		int idx,x,num1=0,num2=0;
		cin>>idx>>x;
		for(int i=max(1,idx-3);i<=min(idx+3,m-2);i++)  num1+=cal(i);
		a[idx]=x;
		for(int i=max(1,idx-3);i<=min(idx+3,m-1);i++)
			if(lca(a[i],a[i+1])==a[i])  b[i]=0;
			else if(lca(a[i],a[i+1])==a[i+1])  b[i]=1;
			else  b[i]=2;
		/*cout<<"a:";
		for(int i=1;i<=m;i++)  cout<<a[i]<<" ";
		cout<<endl;
		cout<<"b:";
		for(int i=1;i<m;i++)  cout<<b[i]<<" ";
		cout<<endl;*/
		for(int i=max(1,idx-3);i<=min(idx+3,m-2);i++)  num2+=cal(i);
		ans+=num2-num1;
		cout<<ans<<endl;
	}
}
/*
5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3
*/
/*
4 3 1
1 2
2 3
2 4
3 1 4
*/
/*
8 6 4
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3 4 5 6 7
*/
/*
30 3 1
10 24
10 13
10 26
13 29
27 26
17 24
27 21
17 15
13 5
13 30
27 3
18 21
9 21
2 24
10 4
11 5
2 8
10 23
1 18
21 25
4 20
12 23
22 27
28 27
18 7
13 6
14 30
10 19
16 21
30 1 17
*/
//14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 12616kb

input:

5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3

output:

4
4
5

result:

ok 3 number(s): "4 4 5"

Test #2:

score: 0
Accepted
time: 3ms
memory: 11420kb

input:

30 200 200
10 24
10 13
10 26
13 29
27 26
17 24
27 21
17 15
13 5
13 30
27 3
18 21
9 21
2 24
10 4
11 5
2 8
10 23
1 18
21 25
4 20
12 23
22 27
28 27
18 7
13 6
14 30
10 19
16 21
14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16 2...

output:

174
175
175
175
175
175
175
175
175
175
176
176
176
176
176
176
175
175
175
175
174
173
173
173
173
173
173
174
174
174
174
173
173
174
174
174
174
174
174
174
174
174
173
173
173
174
173
173
174
173
174
174
174
174
174
174
174
174
174
174
174
175
174
174
174
174
174
175
175
177
177
177
177
177
176
...

result:

ok 200 numbers

Test #3:

score: 0
Accepted
time: 332ms
memory: 10632kb

input:

1000 200000 200000
142 266
266 877
877 673
673 473
923 473
923 55
55 288
679 288
85 679
85 460
296 460
793 296
262 793
40 262
40 680
647 680
999 647
56 999
550 56
550 774
774 939
939 423
423 168
168 554
554 93
329 93
329 474
221 474
890 221
890 304
752 304
345 752
345 269
290 269
290 781
781 264
859...

output:

133598
133598
133598
133598
133598
133598
133596
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133596
133596
133596
133596
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133598
133596
133596
133596
133596
133596...

result:

ok 200000 numbers

Test #4:

score: 0
Accepted
time: 324ms
memory: 11732kb

input:

1000 200000 200000
911 577
911 775
845 911
911 780
911 585
786 911
725 911
960 911
911 645
949 911
46 911
911 429
714 911
911 703
999 911
911 194
166 911
984 911
911 262
902 911
911 201
680 911
637 911
911 923
697 911
911 534
911 38
911 743
911 762
911 342
911 983
911 758
911 716
48 911
27 911
491 9...

output:

199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810
199810...

result:

ok 200000 numbers

Test #5:

score: 0
Accepted
time: 356ms
memory: 12024kb

input:

1000 200000 200000
481 469
250 469
751 469
932 751
469 496
779 932
932 277
154 481
836 932
313 496
157 250
723 277
496 625
824 723
252 496
932 50
836 349
313 348
580 252
277 381
183 932
648 252
824 81
250 310
338 154
481 441
932 772
779 534
310 972
513 836
98 534
678 183
902 469
349 370
380 348
751 ...

output:

193586
193586
193586
193585
193586
193586
193586
193586
193586
193586
193586
193586
193586
193586
193586
193587
193588
193588
193588
193588
193588
193588
193588
193588
193587
193588
193588
193589
193589
193589
193589
193589
193589
193590
193590
193590
193590
193590
193590
193590
193590
193590
193590...

result:

ok 200000 numbers

Test #6:

score: 0
Accepted
time: 331ms
memory: 10672kb

input:

1000 200000 200000
135 730
730 138
545 135
179 730
170 135
282 545
282 852
852 664
61 664
243 664
852 68
838 135
68 822
282 370
698 135
179 304
170 225
496 664
179 234
545 397
950 397
698 550
304 987
730 605
671 698
730 458
550 318
170 754
243 468
159 671
852 414
159 928
61 443
664 705
234 75
170 47...

output:

197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197896
197897
197897
197897
197897
197897
197897
197897
197897
197897
197897
197897
197897
197897
197897...

result:

ok 200000 numbers

Test #7:

score: 0
Accepted
time: 1153ms
memory: 32624kb

input:

200000 200000 200000
14041 108064
14041 6424
164394 6424
118940 164394
118940 153965
71525 153965
71525 23275
23275 136661
136661 78274
75990 78274
75990 39081
163771 39081
163771 159683
159683 104966
104966 15146
15146 85180
181282 85180
181282 44830
44830 86055
86055 164641
18858 164641
18858 1800...

output:

133599
133599
133599
133599
133599
133599
133599
133597
133597
133597
133595
133595
133593
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133595
133593
133593
133593
133593
133591
133591
133591
133591
133591
133591...

result:

ok 200000 numbers

Test #8:

score: 0
Accepted
time: 477ms
memory: 33536kb

input:

200000 200000 200000
62780 76814
47775 76814
110514 76814
115498 76814
76814 185747
76814 76605
76814 153854
61935 76814
76814 22798
191569 76814
84863 76814
65861 76814
182858 76814
164850 76814
170036 76814
76814 171051
76814 177452
76176 76814
76814 148390
76814 152812
76814 11154
76814 134237
13...

output:

199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999
199999...

result:

ok 200000 numbers

Test #9:

score: 0
Accepted
time: 762ms
memory: 32452kb

input:

200000 200000 200000
99629 142514
178276 142514
115655 142514
99629 178074
178276 175567
70738 175567
115655 129972
89322 129972
169894 129972
147071 129972
10566 175567
107243 129972
8907 142514
7782 169894
110752 7782
147071 76195
115655 114377
7782 121893
101071 10566
84377 121893
175567 160127
1...

output:

197382
197381
197381
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197382
197381
197381
197381
197381
197381
197380
197380
197380
197380
197380
197380
197380
197380
197380
197380
197380
197380
197380
197380
197380...

result:

ok 200000 numbers

Test #10:

score: 0
Accepted
time: 635ms
memory: 32752kb

input:

200000 200000 200000
43091 180583
9077 43091
53566 9077
9077 167067
53566 19150
23945 53566
19150 154823
43091 175394
23945 53451
8199 180583
165028 8199
142301 8199
134062 53566
42947 154823
53451 70553
19150 171332
8199 134312
134062 53691
142301 185642
153308 70553
142301 107541
53566 172393
1651...

output:

199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974
199974...

result:

ok 200000 numbers

Test #11:

score: 0
Accepted
time: 142ms
memory: 32728kb

input:

200000 1 200000
197983 124070
174059 197983
10252 197983
20970 197983
160835 10252
174059 165013
152731 165013
10252 56326
152731 125850
20970 82906
114208 174059
28990 124070
28990 5953
9385 125850
174059 198622
151867 198622
23092 56326
55184 124070
18287 160835
135931 10252
104549 55184
82256 198...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 numbers

Test #12:

score: 0
Accepted
time: 157ms
memory: 32684kb

input:

200000 2 200000
29068 50187
50187 120936
163187 50187
186138 50187
29068 115846
5735 29068
152896 50187
115846 24968
151823 24968
183803 163187
29068 152721
152721 47799
29068 196869
29068 152775
5023 186138
27368 24968
115846 112237
13012 50187
112237 85883
24968 51691
61801 183803
112237 85045
521...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 200000 numbers

Test #13:

score: 0
Accepted
time: 318ms
memory: 32928kb

input:

200000 3 200000
79577 85741
164484 79577
41699 79577
132056 41699
39180 132056
182376 41699
97496 39180
164484 132037
45902 85741
183818 97496
182376 91448
135302 97496
85566 164484
56863 91448
41699 34451
132056 105308
164884 164484
135302 52544
8156 85741
187216 79577
79577 154465
90451 164484
391...

output:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

result:

ok 200000 numbers

Extra Test:

score: 0
Extra Test Passed