QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330914#7767. 数据结构liuhangxin0 1142ms310696kbC++144.4kb2024-02-17 20:49:412024-02-17 20:49:42

Judging History

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

  • [2024-02-17 20:49:42]
  • 评测
  • 测评结果:0
  • 用时:1142ms
  • 内存:310696kb
  • [2024-02-17 20:49:41]
  • 提交

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,int 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];
		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]);
	}
	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;j++,x=f[x])
			for(pii t:kf[x][i-j])
			kdis[u][i].push_back(t);
		merge(kdis[u][i]);
	}
	merge(tr[u]);
}
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()
{
	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);
	dfs3(1,0);
	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);
			getpath(x,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: 18ms
memory: 98336kb

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:

63813746668
39706791136
41564728985548
42540773244
121482887432
39364631015830
192080633293713
222053365360
160651365198526
58443325738
148624226971416
86429859858
129989122842
229619604627205
103973077436
356223942862388
51496190160
115658467372
82893877703
139223400080
229421255832
95104574163
198...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 1126ms
memory: 305472kb

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
617528288
617528288
1420484825030
45822091130
349250110352
322280427224
135744407868
1662473271302
1811197159865
110296676908
2213032527764
2667529773780
339104513688
344421089520
2168667686253
301069727060
74741665870800
2713010572002
179479423105627
1737685482768
4496553265184
2259517589856
7410...

result:

wrong answer 2nd numbers differ - expected: '0', found: '617528288'

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 569ms
memory: 283536kb

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
987694439181864
294904735015160
20917805624
4212298888
1354054554517552
597518041305560
1430292219687481
2356617911629240
2387977729131424
1264903636419031
2013130649895136
12395717844
6295231442
6295231442
31096948872
82246051928
5053414463990073
5450467434109353
1356343103242207
84323030630
5169...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 1142ms
memory: 310696kb

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
1247170154
2813454720
0
4220182080
5333510560
5333510560
2276086476
5333510560
14378532276
5942095984
36797844924
25928778672
0
3151398896
21286519544
23157597032
27952107880
26512821492
14335620872
14272373408
31583769068
25393717948
14028666558
54960548168
14007203712
3501800928
80998045536
...

result:

wrong answer 4th numbers differ - expected: '0', found: '1247170154'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #2:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%