QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#469279#1163. Another Tree Queries ProblempeterWA 155ms16700kbC++205.9kb2024-07-09 17:01:052024-07-09 17:01:05

Judging History

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

  • [2024-07-09 17:01:05]
  • 评测
  • 测评结果:WA
  • 用时:155ms
  • 内存:16700kb
  • [2024-07-09 17:01:05]
  • 提交

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(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(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]){
		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],dfn[u],-x,1);
		t4.update(1,1,n,dfn[v],dfn[u],x*lu);
	}else{
		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],dfn[v],-x,1);
		t4.update(1,1,n,dfn[u],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);
				trupdate2(u,-1);
				trupdate3(fa[u],-sz[u]);
			}
		}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(fa[lca],tt);
		}else{
			ll res=1ll*dep[u]*t1.tr[1]+t2.tr[1]-2ll*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: 0ms
memory: 16700kb

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: 155ms
memory: 14988kb

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:

866
954
853
1839
2386
1418
3136
2495
4955
4045
4293
3937
5989
4767
6810
7723
4782
8293
7581
10059
7959
6222
11584
7360
13279
15255
9667
9373
8972
11632
18881
23005
16780
18219
11758
14922
12582
19221
12907
18991
25597
22277
26244
20953
15242
23814
14442
21011
14656
26577
20505
31582
21037
34678
1894...

result:

wrong answer 1st numbers differ - expected: '826', found: '866'