QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466926#1163. Another Tree Queries ProblemyinheeWA 110ms12136kbC++145.0kb2024-07-08 11:55:222024-07-08 11:55:25

Judging History

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

  • [2024-07-08 11:55:25]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:12136kb
  • [2024-07-08 11:55:22]
  • 提交

answer

// Problem: A. Another Tree Queries Problem
// Contest: Codeforces - 2020-2021 Winter Petrozavodsk Camp, Day 9 Contest (XXI Open Cup, Grand Prix of Suwon)
// URL: https://codeforces.com/gym/102979/problem/A
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define mems(x,y) memset(x,y,sizeof x)
#define Mp make_pair
#define eb emplace_back
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a);i>=(b);i--)
#define go(i,u) for(int i=head[u];i;i=e[i].nxt)
	typedef long long ll;
	typedef pair<int,int> pii;
	template<typename T>
	il void read(T &x){
		int f=1;x=0;char c=gc();
		while(c<'0'||c>'9'){
			if(c=='-'){
				f=-1;
			}
			c=gc();
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-48,c=gc();
		}
		x*=f;
	}
	template<typename T,typename ...Args>
	void read(T &x,Args &...args){
		read(x),read(args...);
	}
	template<typename T>
	il void write(T x){
		char buf[43];int len=0;
		if(x<0){
			pc('-'),x=-x;
		}
		do{
			buf[++len]=x%10,x/=10;
		}while(x);
		while(len){
			pc(buf[len--]+'0');
		}
	}
}
using namespace my_std;
const int N=2e5+7,M=-1,inf=0x3f3f3f3f,mod=0;
int n,m;
int dep[N],siz[N],son[N],fa[N][23];
int cur,dfn[N],rk[N],top[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
void dfs1(int u,int f){
	siz[u]=1;
	fa[u][0]=f,dep[u]=dep[f]+1;
	rep(i,1,18){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]){
			son[u]=v;
		}
	}
}
void dfs2(int u,int t){
	top[u]=t;
	rk[dfn[u]=++cur]=u;
	if(!son[u]){
		return;
	}
	dfs2(son[u],t);
	go(i,u){
		int v=e[i].to;
		if(v==fa[u][0]||v==son[u]){
			continue;
		}
		dfs2(v,v);
	}
}
struct SGT{
	ll tr[N<<2],f[N<<2][3],tag[N<<2][3];
	il void reset(int o,int op,int k){
		tr[o]+=f[o][op]*k;
		tag[o][op]+=k;
	}
	il void pushup(int o){
		tr[o]=tr[o<<1]+tr[o<<1|1];
	}
	il void pushdown(int o){
		rep(i,0,2){
			reset(o<<1,i,tag[o][i]),reset(o<<1|1,i,tag[o][i]);
			tag[o][i]=0;
		}
	}
	void build(int l,int r,int o){
		if(l==r){
			if(l>1){
				f[o][0]=1;
				f[o][1]=siz[rk[l]];
				f[o][2]=-dep[rk[l]];
			}
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,o<<1),build(mid+1,r,o<<1|1);
		f[o][0]=f[o<<1][0]+f[o<<1|1][0];
		f[o][1]=f[o<<1][1]+f[o<<1|1][1];
		f[o][2]=f[o<<1][2]+f[o<<1|1][2];
	}
	void update(int l,int r,int o,int x,int y,int op,int k){
		if(l>=x&&r<=y){
			reset(o,op,k);
			return;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		if(x<=mid){
			update(l,mid,o<<1,x,y,op,k);
		}
		if(y>mid){
			update(mid+1,r,o<<1|1,x,y,op,k);
		}
		pushup(o);
	}
	ll query(int l,int r,int o,int x,int y){
		if(r<x||l>y){
			return 0;
		}
		if(l>=x&&r<=y){
			return tr[o];
		}
		pushdown(o);
		int mid=(l+r)>>1;
		return query(l,mid,o<<1,x,y)+query(mid+1,r,o<<1|1,x,y);
	}
}T;
il int jump(int u,int k){
	drep(i,18,0){
		if(k>=(1<<i)){
			u=fa[u][i];
			k-=1<<i;
		}
	}
	return u;
}
il 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]][0];
	}
	return dep[u]<dep[v]?u:v;
}
il void update(int u,int v,int op,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		T.update(1,n,1,dfn[top[u]],dfn[u],op,k);
		u=fa[top[u]][0];
	}
	if(dfn[u]>dfn[v]){
		swap(u,v);
	}
	if(dfn[u]<dfn[v]){
		T.update(1,n,1,dfn[u]+1,dfn[v],op,k);
	}
}
il ll query(int u,int v){
	ll ret=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		ret+=T.query(1,n,1,dfn[top[u]],dfn[u]);
		u=fa[top[u]][0];
	}
	if(dfn[u]>dfn[v]){
		swap(u,v);
	}
	if(dfn[u]<dfn[v]){
		ret+=T.query(1,n,1,dfn[u]+1,dfn[v]);
	}
	return ret;
}
void Yorushika(){
	read(n);
	rep(i,1,n-1){
		int u,v;read(u,v);
		add(u,v),add(v,u);
	}
	dfs1(1,0),dfs2(1,1);
	T.build(1,n,1);
	read(m);
	ll sum=0;
	while(m--){
		int op,x,y;
		read(op,x);
		if(op==1){
			read(y);
			if(x==y){
				x=y=1;
			}
			if(dep[x]<=dep[y]||jump(x,dep[x]-dep[y])!=y){
				T.update(1,n,1,dfn[y],dfn[y]+siz[y]-1,1,1);
				update(1,fa[y][0],0,siz[y]);
				sum+=siz[y];
			}else{
				int u=jump(x,dep[x]-dep[y]-1);
				T.update(1,n,1,1,dfn[u]-1,1,1);
				T.update(1,n,1,dfn[u]+siz[u],n,1,1);
				update(1,y,0,-siz[u]);
				sum+=n-siz[u];
			}
		}else if(op==2){
			read(y);
			int u=getLca(x,y);
			update(x,u,2,1),update(x,u,0,1+dep[x]);
			update(y,u,2,1),update(y,u,0,1+dep[y]);
			update(1,u,0,dep[x]+dep[y]-2*dep[u]+1);
			sum+=dep[x]+dep[y]-2*dep[u]+1;
		}else{
			ll ans=T.tr[1];
			if(x==1){
				printf("%lld\n",ans);
			}else{
				ans+=1ll*(dep[x]-1)*sum-2*query(1,x);
				printf("%lld\n",ans);
			}
		}
		assert(!T.query(1,n,1,1,1));
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10068kb

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: 110ms
memory: 12136kb

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
8437
11003
18272
22174
16139
17660
11063
14291
12045
18630
12368
17355
23696
20714
24792
20021
13962
22060
13163
19488
13321
25000
19336
30022
19846
33622
17483...

result:

wrong answer 2782nd numbers differ - expected: '1132082', found: '1131891'