QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#469324 | #1163. Another Tree Queries Problem | peter | WA | 153ms | 16684kb | C++20 | 6.2kb | 2024-07-09 17:32:38 | 2024-07-09 17:32:38 |
Judging History
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'