QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#474238 | #1163. Another Tree Queries Problem | czc | RE | 0ms | 0kb | C++23 | 5.4kb | 2024-07-12 16:51:40 | 2024-07-12 16:51:41 |
answer
#include <bits/stdc++.h>
#define marry return
// #define int long long
#define lowbit(x) (x&-x)
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57)f=ch=='-'?-1:1,ch=getchar();
while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=getchar();
return x*f;}
using namespace std;
const int inf=1e18;
const int F=0;
const int mod=114514;
int n,m;
struct node{
int nx,to;
}w[400005];
int head[200005],t;
void add(int a,int b) { w[++t]={head[a],b},head[a]=t; }
int top;
int siz[200005],dfn[200005];
int pl[200005],pr[200005];
int son[200005],fa1[200005],fa2[200005];
int dep[200005];
long long ds[200005];
inline void shupoudfs1(int s,int fa)
{
ds[s]=dep[s]=dep[fa]+1;
fa2[s]=fa;
siz[s]=1;
for(int i=head[s];i;i=w[i].nx)
{
int vi=w[i].to;
if(vi==fa)
continue;
shupoudfs1(vi,s);
ds[s]+=ds[vi];
siz[s]+=siz[vi];
}
}
inline void shupoudfs2(int s,int fa)
{
dfn[++top]=s;
pl[s]=top;
int mx=0;
for(int i=head[s];i;i=w[i].nx)
{
int vi=w[i].to;
if(vi==fa)
continue;
if(siz[vi]>siz[mx])
mx=vi;
}
if(mx)
fa1[mx]=fa1[s],
shupoudfs2(mx,s),
son[s]=son[mx];
else
son[s]=s;
for(int i=head[s];i;i=w[i].nx)
{
int vi=w[i].to;
if(vi==fa||vi==mx)
continue;
fa1[vi]=vi;
shupoudfs2(vi,s);
}
pr[s]=top;
}
void shupou(int st)
{
shupoudfs1(st,0);
top=0,fa1[st]=st;
shupoudfs2(st,0);
}
long long cal(int siz) { marry 1ll*siz*(siz-1)/2; }
struct segment_tree1{
#define b1 (b<<1)
#define b2 (b<<1|1)
#define mid ((l+r)>>1)
long long sum[800005];
int tag1[800005],sz[800005];
long long sumsiz[800005];
long long tag2[800005],tag3[800005];
void pushup(int b) { sum[b]=sum[b1]+sum[b2]; }
void pushdown(int b)
{
if(tag1[b])
{
sum[b1]+=sumsiz[b1]*tag1[b];
sum[b2]+=sumsiz[b2]*tag1[b];
tag1[b1]+=tag1[b],tag1[b2]+=tag1[b];
tag1[b]=0;
}
if(tag2[b])
{
sum[b1]+=tag2[b]*sz[b1],sum[b2]+=tag2[b]*sz[b2];
tag2[b1]+=tag2[b],tag2[b2]+=tag2[b];
tag2[b]=0;
}
if(tag3[b])
{
sum[b2]+=(cal(sz[b2]))*tag3[b];
sum[b1]+=(cal(sz[b])-cal(sz[b2]))*tag3[b];
tag3[b1]+=tag3[b],tag3[b2]+=tag3[b];
tag2[b1]+=sz[b2]*tag3[b];
tag3[b]=0;
}
}
void build(int l,int r,int b)
{
sz[b]=r-l+1;
if(l==r)
marry sumsiz[b]=siz[dfn[l]],void();
build(l,mid,b1);
build(mid+1,r,b2);
sumsiz[b]=sumsiz[b1]+sumsiz[b2];
}
long long query(int l,int r,int b,int ll,int rr)
{
if(l>=ll&&r<=rr)
marry
// printf("?%d %d %d\n",l,r,sum[b]),
sum[b];
pushdown(b);
long long res=0;
if(mid>=ll)
res+=query(l,mid,b1,ll,rr);
if(mid<rr)
res+=query(mid+1,r,b2,ll,rr);
marry res;
}
void add1(int l,int r,int b,int ll,int rr,int val)
{
// if(b==1)
// printf("1+%d %d %d\n",ll,rr,val);
if(l>=ll&&r<=rr)
{
sum[b]+=sumsiz[b]*val;
tag1[b]+=val;
marry;
}
pushdown(b);
if(mid>=ll)
add1(l,mid,b1,ll,rr,val);
if(mid<rr)
add1(mid+1,r,b2,ll,rr,val);
pushup(b);
}
int x,k;
void add2(int l,int r,int b,int ll,int rr)
{
// if(b==1)
// printf("2+%d %d %d %d\n",ll,rr,x,k);
if(l>=ll&&r<=rr)
{
if(k)
{
sum[b]+=(cal(rr-l+1)-cal(rr-r))*k;
tag3[b]+=k;
tag2[b]+=1ll*(rr-r)*k;
}
sum[b]+=1ll*sz[b]*x;
tag2[b]+=x;
marry;
}
pushdown(b);
if(mid>=ll)
add2(l,mid,b1,ll,rr);
if(mid<rr)
add2(mid+1,r,b2,ll,rr);
pushup(b);
}
void print(int l,int r,int b)
{
printf("%d %d %d\n",l,r,sum[b]);
if(l==r)
marry;
print(l,mid,b1);
print(mid+1,r,b2);
}
}T;
long long sumA,sumdep;
void addline(int s,int val)
{
if(s==0)
marry;
T.k=0,T.x=val;
T.add2(1,n,1,pl[fa1[s]],pl[s]);
addline(fa2[fa1[s]],val);
}
int lca(int x,int y,int X,int Y)
{
if(fa1[x]==fa1[y])
{
if(dep[x]<dep[y])
swap(x,y),swap(X,Y);
T.x=dep[X]-dep[x]+1,T.k=1;
if(pl[y]<pl[x])
T.add2(1,n,1,pl[y]+1,pl[x]);
marry y;
}
if(dep[fa1[x]]<dep[fa1[y]])
swap(x,y),swap(X,Y);
T.x=dep[X]-dep[x]+1,T.k=1;
T.add2(1,n,1,pl[fa1[x]],pl[x]);
marry lca(fa2[fa1[x]],y,X,Y);
}
long long query(int p)
{
if(p==0)
marry 0;
marry T.query(1,n,1,pl[fa1[p]],pl[p])+query(fa2[fa1[p]]);
}
void solve()
{
int opt=read();
if(opt==1)
{
int x=read(),p=read();
if(x==p)
{
T.add1(1,n,1,1,n,1);
sumA+=n;
sumdep+=ds[1];
}
else if(pl[p]<=pl[x]&&pr[p]>=pr[x])
{
T.add1(1,n,1,1,n,1);
if(pl[p]<pr[p])
T.add1(1,n,1,pl[p]+1,pr[p],-1);
sumA+=n-siz[p]+1;
sumdep+=ds[1]-ds[p]+dep[p];
addline(p,1-siz[p]);
}
else
{
T.add1(1,n,1,pl[p],pr[p],1);
sumA+=siz[p];
sumdep+=ds[p];
if(fa2[p])
addline(fa2[p],siz[p]);
}
}
else if(opt==2)
{
int x=read(),y=read();
int LCA=lca(x,y,x,y);
sumA+=dep[x]+dep[y]-2*dep[LCA]+1;
sumdep+=cal(dep[x]+1)+cal(dep[y]+1)-2*cal(dep[LCA]+1)+dep[LCA];
addline(LCA,dep[x]+dep[y]-2*dep[LCA]+1);
}
else if(opt==3)
{
int p=read();
long long ans=sumA*dep[p];
ans+=sumdep;
ans-=query(p)*2;
printf("%lld\n",ans);
}
}
signed main()
{
freopen("in.in","r",stdin);
freopen("std.out","w",stdout);
n=read();
for(int i=1;i<n;++i)
{
int a=read(),b=read();
add(a,b);
add(b,a);
}
shupou(1);
T.build(1,n,1);
// for(int i=1;i<=n;++i)
// printf("%d ",dfn[i]);
// puts("");
// for(int i=1;i<=n;++i)
// printf("%d ",siz[dfn[i]]);
// puts("");
int t=read();
while(t--)
solve();
marry F;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
5 4 2 2 5 1 5 1 3 5 2 2 4 3 4 2 1 5 2 5 5 3 2