QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#470499 | #1163. Another Tree Queries Problem | maojun | WA | 101ms | 35132kb | C++23 | 2.9kb | 2024-07-10 14:32:35 | 2024-07-10 14:32:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,q;
const int E=N<<1;
int tot=0,head[N],to[E],nxt[E];
inline void Add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
#define go(chk) for(int i=head[u];i;i=nxt[i])if(int v=to[i];chk)
int dfc=0,fa[N],dep[N],siz[N],son[N],top[N],dfn[N],id[N];
void dfs1(int u,int fath){fa[u]=fath;dep[u]=dep[fath]+1;siz[u]=1;go(v^fath){dfs1(v,u);siz[u]+=siz[v];siz[v]>siz[son[u]]&&(son[u]=v);}}
void dfs2(int u,int tp){top[u]=tp;id[dfn[u]=++dfc]=u;if(!son[u])return;dfs2(son[u],tp);go(v^fa[u]&&v^son[u])dfs2(v,v);}
inline int LCA(int u,int v){for(;top[u]^top[v];u=fa[top[u]])if(dep[top[u]]<dep[top[v]])swap(u,v);return dep[u]<dep[v]?u:v;}
inline int gson(int u,int v){int lst;for(;top[u]^top[v];u=fa[lst=top[u]]);return u==v?lst:son[v];}
const int S=N<<2;
ll B[S],SZ[S],DP[S];int ln[S];
struct TAG{
ll a,s,d;TAG():a(0),s(0),d(0){}TAG(int a,int s,int d):a(a),s(s),d(d){}
operator bool(){return a||s||d;}
void operator+=(const TAG&b){a+=b.a;s+=b.s;d+=b.d;}
}tg[S];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
#define Ls ls,l,mid
#define Rs rs,mid+1,r
#define all 1,1,n
inline void pu(int p){B[p]=B[ls]+B[rs];}
inline void chg(int p,TAG k){B[p]+=k.a*ln[p]+k.s*SZ[p]+k.d*DP[p];tg[p]+=k;}
inline void pd(int p){if(tg[p]){chg(ls,tg[p]);chg(rs,tg[p]);tg[p]=TAG();}}
void bld(int p,int l,int r){ln[p]=r-l+1;if(l==r){SZ[p]=siz[id[l]];DP[p]=dep[id[l]];return;}bld(Ls);bld(Rs);SZ[p]=SZ[ls]+SZ[rs];DP[p]=DP[ls]+DP[rs];}
void U(int p,int l,int r,int L,int R,TAG k){if(L<=l&&r<=R)return chg(p,k);pd(p);if(L<=mid)U(Ls,L,R,k);if(R>mid)U(Rs,L,R,k);pu(p);}
ll Q(int p,int l,int r,int L,int R){if(L<=l&&r<=R)return B[p];pd(p);return L>mid?Q(Rs,L,R):R<=mid?Q(Ls,L,R):Q(Ls,L,R)+Q(Rs,L,R);}
ll A=0;
inline void Utree(int u,int k){
A+=siz[u];
U(all,dfn[u],dfn[u]+siz[u]-1,TAG(0,k,0));
k*=siz[u];
for(u=fa[u];u;u=fa[top[u]])U(all,dfn[top[u]],dfn[u],TAG(k,0,0));
}
inline void Upath(int u,int v){
int l=LCA(u,v),du=dep[u]+1,dv=dep[v]+1,d=du+dv-1-dep[l]*2;
A+=d;
for(;top[u]^top[l];u=fa[top[u]])U(all,dfn[top[u]],dfn[u],TAG(du,0,-1));if(u^l)U(all,dfn[l]+1,dfn[u],TAG(du,0,-1));
for(;top[v]^top[l];v=fa[top[v]])U(all,dfn[top[v]],dfn[v],TAG(dv,0,-1));if(v^l)U(all,dfn[l]+1,dfn[v],TAG(dv,0,-1));
for(;l;l=fa[top[l]])U(all,dfn[top[l]],dfn[l],TAG(d,0,0));
}
inline ll Qall(int u){
ll res=dep[u]*A+B[1];
for(;u;u=fa[top[u]])res-=2*Q(all,dfn[top[u]],dfn[u]);
return res;
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);Add(u,v);Add(v,u);}
dfs1(1,0);dfs2(1,1);bld(all);
scanf("%d",&q);
for(int o,u,v;q--;){
scanf("%d%d",&o,&u);
if(o==1){
scanf("%d",&v);
if(u==v)Utree(1,1);
else if(dfn[v]<dfn[u]&&dfn[u]<dfn[v]+siz[v]){Utree(1,1);Utree(gson(u,v),-1);}
else Utree(v,1);
}else if(o==2){scanf("%d",&v);Upath(u,v);}
else printf("%lld\n",Qall(u));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 35132kb
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: 101ms
memory: 34576kb
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 8493 11255 18524 22790 16363 18080 11343 14599 12101 19050 12424 18951 25862 22196 26160 20705 14874 23884 13961 20742 14119 26710 19906 31390 20416 34990 18509...
result:
wrong answer 29th numbers differ - expected: '8437', found: '8493'