QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#470496 | #1163. Another Tree Queries Problem | maojun | TL | 3ms | 35208kb | C++23 | 2.9kb | 2024-07-10 14:24:14 | 2024-07-10 14:24:14 |
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[u]<dfn[v]&&dfn[v]<dfn[u]+siz[u])Utree(v,1);
else{Utree(1,1);Utree(gson(u,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: 3ms
memory: 35208kb
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
Time Limit Exceeded
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 ...