QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330941#7767. 数据结构liuhangxin10 1268ms318328kbC++144.8kb2024-02-17 21:11:172024-02-17 21:11:17

Judging History

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

  • [2024-02-17 21:11:17]
  • 评测
  • 测评结果:10
  • 用时:1268ms
  • 内存:318328kb
  • [2024-02-17 21:11:17]
  • 提交

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;
		}
	}
	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: 23ms
memory: 98024kb

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:

0
0
866944956
0
0
433472478
2797400513982
3447996034
3422226834010
1674542130
2580705822430
1674542130
2601977518
4172869665681
1970283448
5876940667610
492570862
2955425172
1300988759
2601977518
985141724
4221137767
5059140822
4433137758
11420259857812
3104154008
1198834818
43831569640
17706992877
...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 1203ms
memory: 298480kb

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
3288575788
4176911055
0
4745654848
6222845818
0
0
6585551621
0
1424960716
5224818790
9459319003
5224818790
8673060864
0
11610197664
0
0
9587792729
0
0
0
2747489046
12425650803
0
0
11191496476
0
26203160421
0
0
15164651949
14868775382
4739127362
0
16391028892
0
15726757336
0
176790179...

result:

wrong answer 9th numbers differ - expected: '7615073807', found: '3288575788'

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 475ms
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
38336201012364
26918248357976
0
0
38338739596959
38333746483861
77988981576370
95653356124529
96774902656953
97710351122380
151494439192539
0
292392954
292392954
1461964770
13881102848
427543401955315
444106202085724
179351281418256
1876968615
289567928374276
484294649729593
877178862
312780839539...

result:

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

Subtask #4:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 1235ms
memory: 304044kb

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: 676ms
memory: 250884kb

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: 1268ms
memory: 318328kb

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: 1231ms
memory: 303592kb

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: 0
Skipped

Dependency #2:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%