QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#469324#1163. Another Tree Queries ProblempeterWA 153ms16684kbC++206.2kb2024-07-09 17:32:382024-07-09 17:32:38

Judging History

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

  • [2024-07-09 17:32:38]
  • 评测
  • 测评结果:WA
  • 用时:153ms
  • 内存:16684kb
  • [2024-07-09 17:32:38]
  • 提交

answer

// Problem: F - Another Tree Queries Problem
// Contest: Virtual Judge - 2024-07-08 div2D1
// URL: https://vjudge.net/contest/638829#problem/F
// Memory Limit: 1014 MB
// Time Limit: 6000 ms

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;
int dfn[maxn],dfx[maxn],top[maxn],son[maxn];
int fa[maxn],sz[maxn],dep[maxn],tim=0,n;
ll sum[maxn],sum2[maxn];
struct Tree{
	ll tr[maxn<<2],tag[maxn<<2];
	void pushup(int now){
		tr[now]=tr[now<<1]+tr[now<<1|1];
	}
	void pushdown(int now,int l,int r,int op){
		if(!tag[now]) return;
		if(!op){
			int mid=(l+r)>>1;
			tr[now<<1]+=1ll*(mid-l+1)*tag[now];
			tr[now<<1|1]+=1ll*(r-mid)*tag[now];
			tag[now<<1]+=tag[now];
			tag[now<<1|1]+=tag[now];
			tag[now]=0;
		}else if(op==1){
			int mid=(l+r)>>1;
			tr[now<<1]+=1ll*(sum[mid]-sum[l-1])*tag[now];
			tr[now<<1|1]+=1ll*(sum[r]-sum[mid])*tag[now];
			tag[now<<1]+=tag[now];
			tag[now<<1|1]+=tag[now];
			tag[now]=0;
		}else{
			int mid=(l+r)>>1;
			tr[now<<1]+=1ll*(sum2[mid]-sum2[l-1])*tag[now];
			tr[now<<1|1]+=1ll*(sum2[r]-sum2[mid])*tag[now];
			tag[now<<1]+=tag[now];
			tag[now<<1|1]+=tag[now];
			tag[now]=0;
		}
	}
	void update(int now,int l,int r,int ql,int qr,int x){
		if(qr<ql) return;
		if(ql<=l&&qr>=r){
			tr[now]+=1ll*(r-l+1)*x;
			tag[now]+=x;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(now,l,r,0);
		if(ql<=mid) update(now<<1,l,mid,ql,qr,x);
		if(qr>mid) update(now<<1|1,mid+1,r,ql,qr,x);
		pushup(now);
	}
	void update2(int now,int l,int r,int ql,int qr,int x,int op){
		if(qr<ql) return;
		if(ql<=l&&qr>=r){
			if(op==1) tr[now]+=1ll*x*(sum[r]-sum[l-1]);
			else tr[now]+=1ll*x*(sum2[r]-sum2[l-1]);
			tag[now]+=x;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(now,l,r,op);
		if(ql<=mid) update2(now<<1,l,mid,ql,qr,x,op);
		if(qr>mid) update2(now<<1|1,mid+1,r,ql,qr,x,op);
		pushup(now);
	}
	ll query(int now,int l,int r,int ql,int qr,int op){
		if(ql<=l&&qr>=r) return tr[now];
		int mid=(l+r)>>1;
		ll res=0;
		pushdown(now,l,r,op);
		if(ql<=mid) res+=query(now<<1,l,mid,ql,qr,op);
		if(qr>mid) res+=query(now<<1|1,mid+1,r,ql,qr,op);
		return res;
	}
}t1,t2,t3,t4,t5;
struct edge{
	int to,nxt;
}e[maxn<<1];
int head[maxn],len,tttt;

inline void init(){
	memset(head,-1,sizeof(head));
	len=0;
}
void add(int u,int v){
	e[++len].to=v;
	e[len].nxt=head[u];
	head[u]=len;
}

void dfs1(int u,int f){
	fa[u]=f;
	dep[u]=dep[f]+1;
	sz[u]=1;
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==f) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	dfn[u]=++tim;
	dfx[tim]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}

void trupdate(int u,int v,int x){
	int lu=dep[u]+1,lv=dep[v]+1;
	while(top[u]!=top[v]){
		// puts("hello");
		if(dep[top[u]]>dep[top[v]]){
			// printf("kk%d %d %d %d\n",u,top[u],dfn[top[u]],dfn[u]);
			// exit(0);
			t1.update(1,1,n,dfn[top[u]],dfn[u],x);
			t2.update2(1,1,n,dfn[top[u]],dfn[u],x,1);
			t3.update2(1,1,n,dfn[top[u]],dfn[u],-x,1);
			t4.update(1,1,n,dfn[top[u]],dfn[u],x*lu);
			u=fa[top[u]];
		}else{
			// printf("kk%d %d %d %d\n",v,top[v],dfn[top[v]],dfn[v]);
			// fflush(stdout);
			t1.update(1,1,n,dfn[top[v]],dfn[v],x);
			t2.update2(1,1,n,dfn[top[v]],dfn[v],x,1);
			t3.update2(1,1,n,dfn[top[v]],dfn[v],-x,1);
			t4.update(1,1,n,dfn[top[v]],dfn[v],x*lv);
			v=fa[top[v]];
		}
	}
	if(dep[u]>dep[v]){
		t1.update(1,1,n,dfn[v],dfn[u],x);
		t2.update2(1,1,n,dfn[v],dfn[u],x,1);
		t3.update2(1,1,n,dfn[v]+1,dfn[u],-x,1);
		t4.update(1,1,n,dfn[v]+1,dfn[u],x*lu);
	}else{
		// puts("here");
		t1.update(1,1,n,dfn[u],dfn[v],x);
		t2.update2(1,1,n,dfn[u],dfn[v],x,1);
		t3.update2(1,1,n,dfn[u]+1,dfn[v],-x,1);
		t4.update(1,1,n,dfn[u]+1,dfn[v],x*lv);
	}
}
// void trupdate4(int u,int v,int x){
	// int lu=dep[u]+1;
	// while(top[u]!=top[v]){
		// t1.update(1,1,n,dfn[top[u]],dfn[u],x);
		// t2.update2(1,1,n,dfn[top[u]],dfn[u],x,1);
		// t3.update2(1,1,n,dfn[top[u]],dfn[u],-x,1);
		// t4.update(1,1,n,dfn[top[u]],dfn[u],x*lu);
		// tttt=top[u];
		// u=fa[top[u]];
	// }
	// if(u!=v){
		// t1.update(1,1,n,dfn[v]+1,dfn[u],x);
		// t2.update2(1,1,n,dfn[v]+1,dfn[u],x,1);
		// t3.update2(1,1,n,dfn[v]+1,dfn[u],-x,1);
		// t4.update(1,1,n,dfn[v]+1,dfn[u],x*lu);
		// tttt=dfx[dfn[v]+1];
	// }
// }
void trupdate2(int u,int x){
	t1.update(1,1,n,dfn[u],dfn[u]+sz[u]-1,x);
	t2.update2(1,1,n,dfn[u],dfn[u]+sz[u]-1,x,1);
	t5.update2(1,1,n,dfn[u],dfn[u]+sz[u]-1,x,2);
}
void trupdate3(int u,int v){
	while(u){
		t4.update(1,1,n,dfn[top[u]],dfn[u],v);
		u=fa[top[u]];
	}
}
ll trquery(int u){
	ll res=0;
	while(u){
		res+=t3.query(1,1,n,dfn[top[u]],dfn[u],1);
		res+=t4.query(1,1,n,dfn[top[u]],dfn[u],0);
		res+=t5.query(1,1,n,dfn[top[u]],dfn[u],2);
		u=fa[top[u]];
	}
	return res;
}
int getlca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	return u;
}

signed main(){
	
	init();
	
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	}
	
	dfs1(1,0);
	dfs2(1,1);
	
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+dep[dfx[i]];
		sum2[i]=sum2[i-1]+sz[dfx[i]];
	}
	
	int q;
	
	scanf("%d",&q);
	
	for(int _=1;_<=q;_++){
		int op,u,v;
		scanf("%d %d",&op,&u);
		// printf("Test %d OK %d %d\n",_,op,u);
		// fflush(stdout);
		if(op==1){
			scanf("%d",&v);
			if(getlca(u,v)!=v){
				trupdate2(v,1);
				trupdate3(fa[v],sz[v]);
			}else{
				trupdate2(1,1);
				if(u!=v){
					trupdate2(u,-1);
					trupdate3(fa[u],-sz[u]);
				}
				// printf("pp%lld\n",t2.tr[1]);
				// printf("pp%lld %lld %lld\n",t3.query(1,1,n,7,7,1),t4.query(1,1,n,7,7,0),t5.query(1,1,n,7,7,2));
			}
		}else if(op==2){
			scanf("%d",&v);
			int lca=getlca(u,v),tt=dep[u]+dep[v]-2*dep[lca]+1;
			// exit(0);
			trupdate(u,v,1);
			// exit(0);
			trupdate3(lca,tt);
		}else{
			ll res=1ll*dep[u]*t1.tr[1]+t2.tr[1]-2ll*trquery(u);
			// printf("kk%lld %lld %lld\n",t1.tr[1],t2.tr[1],trquery(u));
			printf("%lld\n",res);
		}
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 16684kb

input:

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

output:

1
5

result:

ok 2 number(s): "1 5"

Test #2:

score: -100
Wrong Answer
time: 153ms
memory: 15068kb

input:

200
171 114
50 183
28 68
67 152
139 125
67 55
50 98
106 71
46 42
157 165
42 49
113 12
81 145
105 13
38 96
34 156
24 17
21 191
135 54
174 116
177 157
123 71
95 130
135 193
150 129
25 190
96 93
188 173
90 160
86 187
20 132
199 75
59 195
189 24
40 68
163 83
25 13
73 33
59 50
154 19
146 21
151 67
89 69
...

output:

826
908
813
1785
2288
1320
3038
2403
4809
3933
4123
3791
5819
4597
6632
7523
4562
8021
7393
9809
7647
6024
11272
7024
12979
14995
9349
9115
8640
11194
18583
22521
16414
17731
11266
14410
12272
18701
12595
18425
25031
21707
25828
20621
14666
23236
13838
20399
14020
25931
20025
31058
20535
34324
18216...

result:

wrong answer 29th numbers differ - expected: '8437', found: '8640'