QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473951#1163. Another Tree Queries Problemlichenyu_acWA 211ms16216kbC++146.0kb2024-07-12 15:12:482024-07-12 15:12:50

Judging History

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

  • [2024-07-12 15:12:50]
  • 评测
  • 测评结果:WA
  • 用时:211ms
  • 内存:16216kb
  • [2024-07-12 15:12:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=N*2;

int head[N],ver[M],nxt[M],tot=1;
void Add(int x,int y){
	ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}

int n,m;
int d[N],fa[N],s[N],to[N],f[N][20];
int top[N],dfn[N],id[N],cnt;

void dfs1(int x,int father){
	d[x]=d[father]+1,fa[x]=father,s[x]=1;
	f[x][0]=fa[x];
	for(int t=1;t<20;t++)
		f[x][t]=f[f[x][t-1]][t-1];
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==father)continue;
		dfs1(y,x);
		s[x]+=s[y];
		if(s[y]>s[to[x]])to[x]=y;
	}
}

void dfs2(int x,int t){
	dfn[x]=++cnt,id[cnt]=x,top[x]=t;
	if(to[x])dfs2(to[x],t);
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==fa[x]||y==to[x])continue;
		dfs2(y,x);
	}
}

#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((L+R)>>1)

int add[N<<2],tag[N<<2][2];
int sum[N<<2],len[N<<2];
int sum_dep[N<<2],len_dep[N<<2];
int sum_size[N<<2],len_size[N<<2];

void upd(int p){
	sum[p]=sum[lc]+sum[rc];
	sum_dep[p]=sum_dep[lc]+sum_dep[rc];
	sum_size[p]=sum_size[lc]+sum_size[rc];
}

void spread(int p,int L,int R){
	if(add[p]){
		add[lc]+=add[p],add[rc]+=add[p];
		sum[lc]+=add[p]*len[lc],sum[rc]+=add[p]*len[rc];
		sum_dep[lc]+=add[p]*len_dep[lc],sum_dep[rc]+=add[p]*len_dep[rc];
		add[p]=0;
	}
	if(tag[p][0]&&tag[p][1]){
		if(L==R){
			tag[p][0]=tag[p][1]=0;
			return;
		}
		int k=R==L?0:(tag[p][1]-tag[p][0])/(R-L);
		tag[lc][0]=tag[p][0],tag[lc][1]=tag[p][0]+k*(mid-L);
		tag[rc][0]=tag[p][0]+k*(mid+1-L),tag[rc][1]=tag[p][1];
		sum_size[lc]+=(tag[lc][1]+tag[lc][0])*(mid-L+1)/2;
		sum_size[rc]+=(tag[rc][1]+tag[rc][0])*(R-mid)/2;
		tag[p][0]=tag[p][1]=0;
	}
}

void build(int p,int L,int R){
	if(L==R){
		len_dep[p]=d[id[L]];
		len_size[p]=s[id[L]];
		len[p]=1;
		return;
	}
	build(lc,L,mid),build(rc,mid+1,R),upd(p);
	len[p]=len[lc]+len[rc];
	len_dep[p]=len_dep[lc]+len_dep[rc];
	len_size[p]=len_size[lc]+len_size[rc];
}

void change_subtree(int p,int L,int R,int l,int r,int k){
	spread(p,L,R);
	if(L!=R)spread(lc,L,mid),spread(rc,mid+1,R);
	if(l<=L&&R<=r){
		sum[p]+=k*len[p],sum_dep[p]+=k*len_dep[p],sum_size[p]+=k*len_size[p];
		add[p]+=k;
		return;
	}
	if(l<=mid)change_subtree(lc,L,mid,l,r,k);
	if(r>mid)change_subtree(rc,mid+1,R,l,r,k);
	upd(p);
}

void change_chain(int p,int L,int R,int l,int r,int k){
	spread(p,L,R);
	if(L!=R)spread(lc,L,mid),spread(rc,mid+1,R);
	if(l<=L&&R<=r){
		sum[p]+=k*len[p],sum_dep[p]+=k*len_dep[p];
		add[p]+=k;
		return;
	}
	if(l<=mid)change_chain(lc,L,mid,l,r,k);
	if(r>mid)change_chain(rc,mid+1,R,l,r,k);
	upd(p);
}

void change_chain(int p,int L,int R,int l,int r,int ltag,int rtag){
	spread(p,L,R);
	if(L!=R)spread(lc,L,mid),spread(rc,mid+1,R);
	if(l<=L&&R<=r){
		int k=l==r?0:(rtag-ltag)/(r-l);
		tag[p][0]=ltag+k*(L-l),tag[p][1]=ltag+k*(R-l);
		if(L==R)sum_size[p]+=tag[p][0],tag[p][0]=tag[p][1]=0;
		else sum_size[p]+=(tag[p][0]+tag[p][1])*(R-L+1)/2;
		return;
	}
	if(l<=mid)change_chain(lc,L,mid,l,r,ltag,rtag);
	if(r>mid)change_chain(rc,mid+1,R,l,r,ltag,rtag);
	upd(p);
}

int ask(int p,int L,int R,int l,int r){
	spread(p,L,R);
	if(L!=R)spread(lc,L,mid),spread(rc,mid+1,R);
	if(l<=L&&R<=r)return sum_size[p];
	if(r<=mid)return ask(lc,L,mid,l,r);
	else if(l>mid)return ask(rc,mid+1,R,l,r);
	else return ask(lc,L,mid,l,r)+ask(rc,mid+1,R,l,r);
}

int ask(int dat[],int p,int L,int R,int x){
	if(L!=R)spread(lc,L,mid),spread(rc,mid+1,R);
	if(L==R)return dat[p];
	if(x<=mid)return ask(dat,lc,L,mid,x);
	else return ask(dat,rc,mid+1,R,x);
}

void print(int dat[]){
	for(int i=1;i<=n;i++)
		printf("%d ",ask(dat,1,1,n,i));
	puts("");
}

#undef lc 
#undef rc
#undef mid

int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return d[x]<d[y]?x:y;
}

int get_son(int p,int x){
	for(int i=19;i>=0;i--)
		if(d[f[x][i]]>p)x=f[x][i];
	return x;
}

void change_subtree(int p,int x){
	if(p==x){
		change_subtree(1,1,n,1,n,1);
	}else if(dfn[x]<=dfn[p]&&dfn[p]<=dfn[x]+s[x]-1){
		int son=get_son(p,x);
		change_subtree(1,1,n,1,n,1);
		change_subtree(1,1,n,dfn[p],dfn[p]+s[p]-1,-1);
	}else{
		change_subtree(1,1,n,dfn[x],dfn[x]+s[x]-1,1);
	}
}

void change_chain(int x,int y){
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])swap(x,y);
		change_chain(1,1,n,dfn[top[x]],dfn[x],1);
		x=fa[top[x]];
	}
	if(dfn[x]>dfn[y])swap(x,y);
	change_chain(1,1,n,dfn[x],dfn[y],1);
}

void add_chain(int x,int k){
	int depth=d[x];
	while(top[x]!=1){
		int ladd=k*(depth-d[top[x]]+1);
		int radd=k*(depth-d[x]+1);
		// printf("change:%d %d %d %d\n",top[x],x,ladd,radd);
		change_chain(1,1,n,dfn[top[x]],dfn[x],ladd,radd);
		x=fa[top[x]];
	}
	int ladd=k*(depth-d[1]+1);
	int radd=k*(depth-d[x]+1);
	// printf("change:%d %d %d %d\n",1,x,ladd,radd);
	change_chain(1,1,n,1,dfn[x],ladd,radd);
}

int ask_chain(int x){
	int ans=0;
	while(top[x]!=1){
		ans+=ask(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	ans+=ask(1,1,n,1,dfn[x]);
	return ans;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		Add(x,y),Add(y,x);
	}
	dfs1(1,0),dfs2(1,1),build(1,1,n);
	// for(int i=1;i<=n;i++)printf("%d ",id[i]);
	// puts("");
	scanf("%d",&m);
	while(m--){
		int op,x,y;
		scanf("%d%d",&op,&x);
		if(op==1){
			scanf("%d",&y);
			change_subtree(x,y);
		}else if(op==2){
			scanf("%d",&y);
			// printf("sum_size:  "),print(sum_size);
			change_chain(x,y);
			int p=LCA(x,y);
			// printf("sum_size:  "),print(sum_size);
			
			add_chain(x,1);
			// printf("step1: sum_size:  "),print(sum_size);
			add_chain(y,1);
			// printf("step2: sum_size:  "),print(sum_size);
			add_chain(p,-1);
			// printf("step3: sum_size:  "),print(sum_size);
			if(p!=1)add_chain(fa[p],-1);
			// printf("step4: sum_size:  "),print(sum_size);
		}else{
			// printf("%d %d %d\n",sum[1]*d[x],sum_dep[1],ask_chain(x));
			printf("%d\n",sum[1]*d[x]+sum_dep[1]-2*ask_chain(x));
		}
		// printf("sum:  "),print(sum);
		// printf("sum_dep:  "),print(sum_dep);
		// printf("sum_size:  "),print(sum_size);
		// puts("");
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 16216kb

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: 211ms
memory: 14208kb

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:

7366
16461
6626
16918
19750
24440
27834
23058
43219
32493
51439
38561
64291
59857
89611
66808
42586
115376
61102
87777
104322
53142
151308
110880
102886
113653
86719
70333
85432
131220
117257
239562
119725
173665
163928
158456
76030
195358
86602
222481
260277
215193
186152
127741
158419
238341
15266...

result:

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