QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629015#7608. Cliquesucup-team4992RE 266ms35060kbC++203.7kb2024-10-11 01:13:382024-10-11 01:13:38

Judging History

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

  • [2024-10-11 01:13:38]
  • 评测
  • 测评结果:RE
  • 用时:266ms
  • 内存:35060kb
  • [2024-10-11 01:13:38]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a,i##end=b; i<=i##end; i++)
#define drep(i,a,b) for(int i=a,i##end=b; i>=i##end; i--)
#define repp(i,a,b) for(int i=a,i##end=b; i<i##end; i++)
#define drepp(i,a,b) for(int i=a,i##end=b; i>i##end; i--)
#define Erep(i,x) for(int i=head[x]; i; i=Edge[i].nxt)
#define Srep(i,x) for(int i=x,i##end=x; i; i=(i-1)&i##end)
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define fi first
#define se second
#define PII pair<int,int>
#define coint const int
#define ms(x,a) memset(x,a,sizeof x)
#define CM cerr<<(&S2-&S1)/1024.<<"KB"<<endl
//std::mt19937_64 Rnd {std::chrono::steady_clock::now().time_since_epoch().count()};
// Rnd();
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
using namespace std;
template<class T>inline T lowbit(const T &x) { return x&-x; }

coint N=2e5+5;
coint mod=1e9+7,inv2=500000004;

int n;
ll fpow[N],inv[N];
vector<int>Edge[N];
int tp[N],f[N],sz[N],son[N],dep[N];
int L[N],R[N],dfn[N],tot;

void Init(){
	fpow[0]=1;
	inv[0]=1;
	rep(i,1,N-5){
		fpow[i]=fpow[i-1]*2%mod;
		inv[i]=inv[i-1]*inv2%mod;
	}
}

void dfs(int x, int fa){
	sz[x]=1; f[x]=fa; dep[x]=dep[fa]+1;
	int &SON=son[x];
	SON=-1;
	for(int y:Edge[x]){
		if(y==fa) continue;
		dfs(y,x);
		sz[x]+=sz[y];
		if(SON==-1 || sz[SON]<sz[y]) SON=y;
	}
}

void dfs_top(int x, int fa, int top){
	L[x]=++tot; dfn[tot]=x;
	tp[x]=top;
	coint &SON=son[x];
	if(SON!=-1) dfs_top(SON,x,top);
	for(int y:Edge[x]){
		if(y!=fa && y!=SON) dfs_top(y,x,y);
	}
	R[x]=tot;
}

ll check(int x){
	return x>=0?fpow[x]:inv[-x];
}

struct Segment_Tree{
	ll sum[N<<1];
	int lazy[N<<1];
	void Up(coint &p){
		coint ls=p<<1,rs=ls|1;
		sum[p]=(sum[ls]+sum[rs])%mod;
	}
	void Down(coint &p){
		if(!lazy[p]) return;
		coint ls=p<<1,rs=ls|1,res=lazy[p];
		sum[ls]=sum[ls]*check(res)%mod; lazy[ls]+=res;
		sum[rs]=sum[rs]*check(res)%mod; lazy[rs]+=res;
		lazy[p]=0; return;
	}
	void Build(coint &p, coint &l, coint &r){
		lazy[p]=0;
		if(l==r){
			sum[p]=1;
			return;
		}
		coint mid=(l+r)>>1,ls=p<<1,rs=ls|1;
		Build(ls,l,mid); Build(rs,mid+1,r);
		Up(p);
	}
	void Upd(coint &p, coint &l, coint &r, coint &L, coint &R, coint &val){
		if(l==L && r==R){
			sum[p]*=check(val); sum[p]%=mod;
			lazy[p]+=val;
			return;
		}
		Down(p);
		coint mid=(l+r)>>1,ls=p<<1,rs=ls|1;
		if(R<=mid) Upd(ls,l,mid,L,R,val);
		else if(L>mid) Upd(rs,mid+1,r,L,R,val);
		else Upd(ls,l,mid,L,mid,val),Upd(rs,mid+1,r,mid+1,R,val);
		Up(p); return;
	}
}sgtr1,sgtr2;

void Add(int x, int y, int val){
	int tpx=tp[x],tpy=tp[y];
	while(tpx!=tpy){
		if(dep[tpx]<dep[tpy]){
//			cout<<"Add "<<y<<" -> "<<tpy<<"\n";
			sgtr1.Upd(1,1,n,L[tpy],L[y],val);
			sgtr2.Upd(1,1,n,L[tpy],L[y],val);
			y=f[tpy];
			tpy=tp[y];
		}else{
//			cout<<"Add "<<x<<" -> "<<tpx<<"\n";
			sgtr1.Upd(1,1,n,L[tpx],L[x],val);
			sgtr2.Upd(1,1,n,L[tpx],L[x],val);
			x=f[tpx];
			tpx=tp[x];
		}
	}
	if(dep[x]>dep[y]) swap(x,y);
//	cout<<"Add "<<y<<" -> "<<x<<"\n";
	sgtr1.Upd(1,1,n,L[x],L[y],val);
	if(x!=y) sgtr2.Upd(1,1,n,L[x]+1,L[y],val);
}

void solve(){
	Init();
	cin>>n;
	rep(i,2,n){
		int x,y;
		cin>>x>>y;
		Edge[x].push_back(y);
		Edge[y].push_back(x);
	}
	dfs(1,0); dfs_top(1,0,1);
	sgtr1.Build(1,1,n); sgtr2.Build(1,1,n);
	int q;
	cin>>q;
	while(q--){
		string opt;
		int a,b;
		cin>>opt>>a>>b;
		Add(a,b,opt=="+"?1:-1);
		cout<<(sgtr1.sum[1]-sgtr2.sum[1]+mod)%mod<<"\n";
	}
	return;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int T=1;
//	cin>>T;
	while(T--) solve();
	return 0;
}
/*

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1
3
7
3
7
9

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 13632kb

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1
3
7
3
7
9

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 13068kb

input:

20
8 7
19 10
12 14
3 16
17 13
7 10
5 6
1 9
15 12
5 2
16 13
3 11
20 14
18 6
1 14
16 20
11 10
3 4
20 6
30
+ 10 20
+ 14 20
+ 12 17
- 14 20
- 12 17
+ 4 6
+ 8 20
+ 3 6
- 10 20
+ 2 17
+ 1 16
+ 6 10
+ 9 10
+ 5 15
+ 7 8
- 7 8
+ 2 5
+ 3 18
+ 1 20
+ 8 16
- 3 18
- 5 15
+ 4 20
+ 14 16
- 4 6
+ 8 19
+ 4 7
- 1 16
...

output:

1
3
7
3
1
3
7
15
7
15
31
63
127
255
257
255
259
515
1027
1283
643
385
769
1537
769
785
865
481
737
369

result:

ok 30 lines

Test #3:

score: 0
Accepted
time: 122ms
memory: 35060kb

input:

131072
3641 72511
10338 18718
8949 15478
79108 62887
42154 28540
65359 102645
93744 48493
3277 103211
43542 61315
93315 118634
24021 57937
31034 436
30411 6208
1388 25159
93424 128520
119820 87281
5860 97559
59648 8225
57244 58766
119685 13716
130165 60958
79806 116338
97486 80167
101963 95499
51263...

output:

1
2
4
8
13
27
43
67
119
215
359
423
847
1167
1935
2447
2975
4511
5023
8639
6911
13759
12991
15103
23295
43775
47999
91647
85375
167295
169343
301695
600703
666239
1332351
2664575
2678911
2687103
5374207
5898495
11731455
11731967
22283263
22807551
21955327
43910399
43911423
44207359
44207360
44469504...

result:

ok 46368 lines

Test #4:

score: 0
Accepted
time: 119ms
memory: 33916kb

input:

131073
52869 122762
63296 22816
9889 23435
9452 109352
95210 125504
104234 105533
42422 123259
31189 77343
88679 25422
13860 61424
49617 27681
71743 44108
2612 55383
89088 79225
49508 86216
45176 26493
60940 104568
10733 11047
118351 29678
6184 107897
69675 73910
39495 78910
14871 125941
64731 68683...

output:

1
3
7
11
15
19
31
35
71
143
287
511
1023
1031
1991
1031
1287
1927
2055
3151
4687
4943
9295
17999
18959
37775
73759
74559
148031
148095
296191
151743
160063
110399
110463
127103
63615
63679
64191
90303
138431
212479
212607
423551
423583
426527
770591
865599
1054015
1794879
3587647
3587903
5168959
743...

result:

ok 38380 lines

Test #5:

score: 0
Accepted
time: 192ms
memory: 26676kb

input:

131072
110424 92279
34180 5104
64611 102341
17972 86901
20410 11042
71530 94889
66017 30180
70335 127390
32167 60823
78004 53470
19518 71917
13638 77859
126902 86404
129728 102154
94425 4299
65248 60503
30607 39590
122443 91908
131032 83134
74541 32476
57016 45547
99821 43007
46700 115397
61041 7605...

output:

1
3
4
8
10
12
18
30
32
43
85
133
267
535
791
927
1567
1663
1791
2111
3391
4031
8063
4031
8063
10111
11263
22527
22543
36879
73487
146959
165391
185871
300559
272655
273183
448031
224015
252431
256527
440847
459279
501791
623647
1069087
1265695
2451487
2455583
4911167
3469375
4341823
4620351
7536767
...

result:

ok 41717 lines

Test #6:

score: 0
Accepted
time: 156ms
memory: 30092kb

input:

131073
67110 38301
121636 116046
93081 73335
44685 130771
105514 33619
39372 105681
75426 78839
116548 46901
69485 76621
124381 35376
22485 127299
100526 68870
59214 63623
65534 67039
7351 74453
99617 88460
99785 107786
105070 57072
122179 1357
125230 70014
95838 127074
119211 24691
41698 112488
502...

output:

1
3
5
11
13
14
18
28
40
52
60
62
122
210
340
532
1032
1192
1448
1968
3393
3391
5471
5631
10303
11071
11199
13183
26239
52223
52735
53759
69375
113407
117503
232191
236287
470271
748799
748807
1410567
2790919
1676807
3155975
6178823
6026759
6068743
12075527
20988423
21185031
42340871
42332419
8409549...

result:

ok 42683 lines

Test #7:

score: 0
Accepted
time: 193ms
memory: 30480kb

input:

131071
73178 110293
100318 26012
15854 39905
73704 8141
15422 88351
37522 86820
75177 113252
27007 40876
114342 57373
114214 99629
77119 106699
111052 54010
7544 43524
6414 93020
81451 90262
65947 86220
34831 11736
54471 103491
42146 26136
11584 28666
50699 22506
114316 26350
106262 53089
31102 8196...

output:

1
3
5
9
4
6
10
18
34
66
85
123
127
255
143
279
559
1007
1535
2559
5023
9375
18655
35167
70335
79039
40031
21599
42079
84063
168127
168831
177919
341759
503295
1006591
1072127
1070079
1976319
2107391
1173503
2347007
4694015
4800511
9601023
18022399
9011199
17563647
34078719
65011711
129564671
1349386...

result:

ok 48590 lines

Test #8:

score: 0
Accepted
time: 266ms
memory: 27908kb

input:

131071
39479 96391
14017 23321
50455 14012
126360 118197
113346 92912
48354 86690
78318 34265
94323 55989
30079 44311
2276 30025
16215 90233
34881 85139
57791 13323
50082 125534
36843 69732
104952 39061
82716 2282
63268 42779
35368 9502
17575 123815
2726 43663
123675 93945
4192 64707
87905 123819
40...

output:

1
3
7
11
23
47
95
111
191
159
319
159
319
321
449
705
1409
2817
1409
2817
2945
5761
11521
11649
23297
46593
62979
96771
96775
190983
381959
762887
1295367
1295623
1296139
2574091
1287051
1549579
2606859
4721419
8950543
17896975
35793935
35810319
71604247
142661655
285274135
570515495
140973600
20810...

result:

ok 48889 lines

Test #9:

score: -100
Runtime Error

input:

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

output:


result: