QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473951 | #1163. Another Tree Queries Problem | lichenyu_ac | WA | 211ms | 16216kb | C++14 | 6.0kb | 2024-07-12 15:12:48 | 2024-07-12 15:12:50 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'