QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330943#7767. 数据结构liuhangxin35 1790ms343044kbC++144.8kb2024-02-17 21:13:312024-02-17 21:13:31

Judging History

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

  • [2024-02-17 21:13:31]
  • 评测
  • 测评结果:35
  • 用时:1790ms
  • 内存:343044kb
  • [2024-02-17 21:13:31]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
int n,m;
vector<int>to[N];
int f[N],top[N],siz[N],son[N],dep[N];
void dfs(int u,int fa)
{
	siz[u]=1;f[u]=fa;dep[u]=dep[fa]+1;
	for(int v:to[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs4(int u,int f,int t){
	top[u]=t;
	if(son[u])dfs4(son[u],u,t);
	for(int v:to[u]){
		if(v==f||v==son[u])continue;
		dfs4(v,u,v);
	}
}
int tot,dfn[N];
#define VP vector<pii>
void merge(VP &nw)
{
	VP ans;
	sort(nw.begin(),nw.end());
	for(pii t:nw)
		if(ans.size()&&ans.back().se+1==t.fi)
			ans.back().se=t.se;
		else ans.push_back(t);
	nw=ans;	
}
void bh(int u,int d)
{
	if(d==0){
		if(!dfn[u])
		dfn[u]=++tot;
		return;
	}
	for(int v:to[u])
	{
		if(v==f[u])continue;
		bh(v,d-1);
	}
}
void dfsbh(int u,int fa)
{
	if(top[u]==u)
	{
		if(!dfn[u])dfn[u]=++tot;
		int nw=u;
		while(son[nw]){
			nw=son[nw];
			if(!dfn[nw])
			dfn[nw]=++tot;
		}
		for(int i=1;i<=3;i++){
			int nw2=u;
			while(nw2){
				for(int v:to[nw2])
					if(v!=son[nw2])
					bh(v,i-1);
				nw2=son[nw2];
			}
		}
	}
	if(son[u])dfsbh(son[u],u);
	for(int v:to[u])
	{
		if(v==fa||v==son[u])continue;
		dfsbh(v,u);
	}
}
struct SEG{
	ull a[N],b[N];
	inline int lowbit(int x){return x&-x;}
	void add(int p,ull v){
		ull x=p*v;
		for(int i=p;i<N;i+=lowbit(i))a[i]+=v,b[i]+=x;
	}
	void Add(int l,int r,int v){
		add(l,v),add(r+1,-v);
	}
	ull Pre(int p){
		ull res=0;
		for(int i=p;i;i-=lowbit(i))res+=a[i]*(p+1)-b[i];
		return res;
	}
	ull qry(int l,int r){return Pre(r)-Pre(l-1);}
}T;
VP tr[N],kdis[N][4],kf[N][4],kans[N][4],kson[N][4];
void Add(VP &nw,VP &x){
	for(pii t:x)nw.push_back(t);
}
void dfs2(int u,int fa)//get
{
	tr[u].push_back({dfn[u],dfn[u]});
	kson[u][0].push_back({dfn[u],dfn[u]});
	for(int v:to[u])
		if(v!=fa){
			dfs2(v,u),Add(tr[u],tr[v]);
			for(int j=0;j<=3;j++)
				kf[v][j]=kson[u][j];
			for(int j=1;j<=3;j++)
			Add(kson[u][j],kson[v][j-1]),merge(kson[u][j]);
		}
	int len=to[u].size();
	VP tmp[4];
	for(int i=len-1;i>=0;i--)
	{
		int v=to[u][i];
		if(v==fa)continue;
		for(int j=1;j<=3;j++)
			Add(kf[v][j],tmp[j]),merge(kf[v][j]);
		for(int j=1;j<=3;j++)
		Add(tmp[j],kson[v][j-1]),merge(tmp[j]);
	}
	merge(tr[u]);
}
void dfs25(int u,int fa)
{
	for(int v:to[u])
		if(v!=fa)
		dfs25(v,u);
	for(int i=0;i<=3;i++)
	{
		for(int j=0;j<=i;j++)
			for(pii t:kson[u][j])
			kdis[u][i].push_back(t);
		for(int j=1,x=u;j<=i&&x;j++,x=f[x])
			for(pii t:kf[x][i-j])
			kdis[u][i].push_back(t);
		merge(kdis[u][i]);
	}
}
void dfs3(int u,int fa)
{
	if(u==1)
	for(int i=0;i<=3;i++)
		kans[u][i]=kdis[u][i];
	else
	for(int i=0;i<=3;i++){
		kans[u][i]=kans[fa][i];
		Add(kans[u][i],kson[u][i]);
		merge(kans[u][i]);
	}
	for(int v:to[u]){
		if(v==fa)continue;
		dfs3(v,u);
	}
}
int lca(int a,int b){
	while(top[a]!=top[b]){
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		a=f[top[a]];
	}
	return dep[a]<dep[b]?a:b;
}
VP getdel(int x,int y,int k){
	VP ans,a=kans[x][k],b=kans[y][k];
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	int lena=a.size(),lenb=b.size();
	for(int i=0,l=0,r=-1;i<lena;i++)
	{
		while(l<lenb&&b[l].se<a[i].fi)l++;
		while(r<lenb-1&&b[r+1].se<=a[i].se)r++;
		if(l>r){
			ans.push_back(a[i]);
			continue;
		}
		int cl=a[i].fi;
		for(int j=l;j<=r;j++)
		{
			if(b[j].fi!=cl)
			ans.push_back({cl,b[j].fi-1});
			cl=b[j].se+1;
		}
		if(cl<=a[i].se)ans.push_back({cl,a[i].se});
	}
	merge(ans);
	return ans;
}
VP getpath(int x,int y,int k)
{
	int l=lca(x,y);
	VP a=getdel(x,l,k);
	VP b=getdel(y,l,k);
	VP c=kdis[l][k];
	Add(a,b);Add(a,c);
	merge(a);
	return a;
}
int main()
{
//	freopen("d3.in","r",stdin);
//	freopen("d.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		to[a].push_back(b);
		to[b].push_back(a);
	}
	dfs(1,0);
	dfs4(1,0,1);
	dfsbh(1,0);
	dfs2(1,0);
	dfs25(1,0);
	dfs3(1,0);
//	for(int i=1;i<=n;i++)
//		cout<<dfn[i]<<" ";puts("");
//	for(int i=1;i<=n;i++)
//	{
//		cout<<i<<endl;
//		for(pii t:kans[i][1])
//			cout<<t.fi<<"!!"<<t.se<<endl;
//	}
	for(int i=1;i<=m;i++)
	{
		int op,x,y,v,k;
		scanf("%d%d",&op,&x);
		if(op==1){
			scanf("%d%d%d",&y,&k,&v);
			VP tmp=getpath(x,y,k);
			for(pii t:tmp)
				T.Add(t.fi,t.se,v);
		}
		else if(op==2){
			scanf("%d",&v);
			for(pii t:tr[x])
				T.Add(t.fi,t.se,v);
		}
		else if(op==3){
			scanf("%d%d",&y,&k);
			VP tmp=getpath(x,y,k);
			ull res=0;
			for(pii t:tmp)
				res+=T.qry(t.fi,t.se);
			printf("%llu\n",res);
		}
		else{
			ull res=0;
			for(pii t:tr[x])
				res+=T.qry(t.fi,t.se);
			printf("%llu\n",res);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 19ms
memory: 95996kb

input:

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

output:

36282180522
2134414313248
2794367845468
1308900968876
1696278722918
2678958746332
6688161965793
2086292026895
5786332239171
2186592622
4014965079076
1674542130
6524658548
7093370803092
10059064557343
11588105409348
492570862
3348941084329
2834694279
4195122521413
4395772262
4221137767
9630829210
991...

result:

wrong answer 1st numbers differ - expected: '37227703492', found: '36282180522'

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 1023ms
memory: 298500kb

input:

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

output:

0
0
0
0
0
0
0
0
7615073807
4176911055
0
4745654848
6222845818
0
0
9739142819
0
1424960716
5224818790
9459319003
13717923473
8673060864
0
11610197664
0
0
9587792729
0
0
0
2747489046
12425650803
0
0
11191496476
0
37597503993
0
0
15164651949
14868775382
15559673116
0
16391028892
0
15726757336
0
2421390...

result:

ok 100169 numbers

Test #4:

score: 0
Accepted
time: 1209ms
memory: 336240kb

input:

200000 200000
121679 2
13340 3
45206 4
112138 5
47397 6
88216 7
173469 8
109861 9
58662 10
130056 11
61155 12
4313 13
196310 14
46189 15
32349 16
143798 17
103215 18
159921 19
27365 20
14332 21
49504 22
64451 23
106931 24
59878 25
177587 26
100555 27
86848 28
793 29
79845 30
150813 31
42854 32
11551...

output:

77900221111
0
0
476439705914
0
216029652830
0
0
631267909751
508097390689
0
29277716182
695169620128
0
809294022024
0
0
829507748883
260130797154
0
1005527232590
109198360548
821333235719
0
0
1265757368752
738460021055
296232170804
845184728833
0
434366813420
0
1922343637889
0
0
0
229703081048
0
441...

result:

ok 100073 numbers

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 457ms
memory: 258836kb

input:

200000 200000
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 51
51 ...

output:

0
134315028896099
38210069287857
75888509018259
25202593262786
179527248054069
75824472356207
156951569638953
246509631358547
251383207461179
181645879044485
285463143130322
213796043841569
244908385583039
53375895750478
450587856840
379327308818961
720758846292557
768646001239774
224741684687567
18...

result:

wrong answer 2nd numbers differ - expected: '134315201201061', found: '134315028896099'

Subtask #4:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 1017ms
memory: 304052kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99786 numbers

Test #8:

score: 0
Accepted
time: 605ms
memory: 250888kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100404 numbers

Test #9:

score: 0
Accepted
time: 1042ms
memory: 318632kb

input:

200000 200000
166945 2
60190 3
101888 4
154621 5
188595 6
175999 7
140051 8
54071 9
167394 10
54228 11
48270 12
14564 13
25727 14
138072 15
77670 16
77795 17
155644 18
171648 19
94412 20
65323 21
130225 22
6359 23
17410 24
8580 25
142556 26
152863 27
166869 28
115234 29
87099 30
160349 31
98200 32
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99768 numbers

Subtask #5:

score: 0
Wrong Answer

Dependency #4:

100%
Accepted

Test #10:

score: 0
Wrong Answer
time: 1009ms
memory: 303588kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 348th numbers differ - expected: '1896761708', found: '948380854'

Subtask #6:

score: 0
Skipped

Dependency #4:

100%
Accepted

Dependency #5:

0%

Subtask #7:

score: 15
Accepted

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Test #17:

score: 15
Accepted
time: 1014ms
memory: 301520kb

input:

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

output:

0
12712803164
0
0
8193968417
14426787309
12950092190
0
32958618613
26764906955
8493139167
0
42785505564
55243799113
0
0
0
0
0
16857343623
27991363871
14151995536
55690427136
85838206842
0
26020925273
22490232861
0
0
1662166464
24948089565
0
26561191640
202942896717
0
91771091757
152033022013
2500525...

result:

ok 100098 numbers

Test #18:

score: 0
Accepted
time: 1790ms
memory: 241084kb

input:

200000 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
...

output:

1506
2433795
1964764
29809
23904
32308
3956297
23683
26194
24496
0
5108618
44498
10494148
1493614
8948
11034059
10983525
9340774
68288
15623342
65908
14673691
63760
62016
68610
3785842
68409
71500
4760847
1843709
83560
86276
3800228
24415019
102280
92867
17894104
25995202
96677
14391781
110124
12872...

result:

ok 99928 numbers

Test #19:

score: 0
Accepted
time: 1116ms
memory: 343044kb

input:

200000 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
...

output:

0
6432
5572
2146
5686
15024
5924
10437
10836
16481
12732
37909
15933
53994
38493
121364
89269
36850
69524
53517
239542
137860
93122
118688
151902
9279
120973
73158
28901
122575
43850
21781
119189
28818
71155
127221
157054
65948
40570
183418
150579
145757
147361
89223
4664
78041
329787
100673
50134
6...

result:

ok 100068 numbers

Subtask #8:

score: 0
Skipped

Dependency #1:

0%