BZOJ 3091:シティツアー
3652 ワード
link cut tree水題
木の鎖を配列と見なして、答えはsigma(a[i]*i*(n-i+1))/C(n+1,2)で、分母は明らかにメンテナンスしなくて、分子は分解してやってみればいいです
(メンテナンス情報のlink cut treeのタグは、TATが即時に有効になる必要があります.そうしないとWAになります)
木の鎖を配列と見なして、答えはsigma(a[i]*i*(n-i+1))/C(n+1,2)で、分母は明らかにメンテナンスしなくて、分子は分解してやってみればいいです
(メンテナンス情報のlink cut treeのタグは、TATが即時に有効になる必要があります.そうしないとWAになります)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
#define mmt(a,v) memset(a,v,sizeof(a))
#define tra(i,u) for(int i=head[u];i;i=e[i].next)
const int N=50000+5;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int fa[N],ch[N][2];
ll sz[N],a1[N],a2[N],add[N],sum[N],w[N];
bool rev[N];
ll sqr(ll x){return x*x;}
ll sum1(ll x){return x*(x+1)/2;}
ll sum2(ll x){return x*(x+1)*(2*x+1)/6;}
ll c2(ll x){return x*(x-1)/2;}
ll calc(int x){
return a1[x]*(sz[x]+1)-a2[x];
}
void pushup(int x){
int l=ch[x][0],r=ch[x][1];
sz[x]=sz[l]+sz[r]+1;
sum[x]=sum[l]+sum[r]+w[x];
a1[x]=a1[l]+w[x]*(sz[l]+1)+a1[r]+sum[r]*(sz[l]+1);
a2[x]=a2[l]+w[x]*sqr(sz[l]+1)+a2[r]+sqr(sz[l]+1)*sum[r]+2*(sz[l]+1)*(a1[r]);
}
void workadd(int x,ll d){
w[x]+=d;
sum[x]+=d*sz[x];
a1[x]+=d*sum1(sz[x]);
a2[x]+=d*sum2(sz[x]);
}
void workrev(int x){
swap(ch[x][0],ch[x][1]);
a2[x]=a2[x]+sqr(sz[x]+1)*sum[x]-2*(sz[x]+1)*a1[x];
a1[x]=sum[x]*(sz[x]+1)-a1[x];
}
void pushdown(int x){
int l=ch[x][0],r=ch[x][1];
if(rev[x]){
rev[l]^=1;rev[r]^=1;
if(l)workrev(l);
if(r)workrev(r);
rev[x]^=1;
}
if(add[x]){
if(l)add[l]+=add[x],workadd(l,add[x]);
if(r)add[r]+=add[x],workadd(r,add[x]);
add[x]=0;
}
}
void debug(int x){
if(!x)return;
pushdown(x);
debug(ch[x][0]);
printf("%d %d %d
",x,ch[x][0],ch[x][1]);
debug(ch[x][1]);
}
bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rotate(int x){
int y=fa[x],z=fa[y],l=ch[y][1]==x,r=l^1;
if(!isroot(y))ch[z][ch[z][1]==y]=x;
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];ch[x][r]=y;
pushup(y);pushup(x);
}
int st[N],tp;
void splay(int x){
st[tp=1]=x;
for(int i=x;!isroot(i);i=fa[i])st[++tp]=fa[i];
while(tp)pushdown(st[tp--]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y)){
if(ch[y][0]==x^ch[z][0]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
for(int t=0;x;t=x,x=fa[x])
splay(x),ch[x][1]=t,pushup(x);
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;workrev(x);
}
int find(int x){
access(x);splay(x);
while(ch[x][0])x=ch[x][0];
return x;
}
void link(int x,int y){
if(find(x)==find(y))return;
makeroot(x);fa[x]=y;
}
void split(int x,int y){
makeroot(x);access(y);splay(y);
}
int pre(int x){
x=ch[x][0];
while(ch[x][1])x=ch[x][1];
return x;
}
void cut(int x,int y){
if(find(x)!=find(y))return;
split(x,y);
if(x!=pre(y))return;
ch[y][0]=fa[x]=0;pushup(y);
}
void query(int x,int y){
if(find(x)!=find(y)){
puts("-1");
return;
}
split(x,y);
ll a=calc(y),b=c2(sz[y]+1),c=gcd(a,b);
printf("%lld/%lld
",a/c,b/c);
}
void update(int x,int y,int d){
if(find(x)!=find(y))return;
split(x,y);
add[y]+=d;workadd(y,d);
}
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int n,m;scanf("%d%d",&n,&m);
rep(i,1,n){
scanf("%lld",&w[i]);
sum[i]=a1[i]=a2[i]=w[i];
sz[i]=1;
}
rep(i,2,n){
int u,v;scanf("%d%d",&u,&v);
link(u,v);
}
while(m--){
int opt,u,v;
scanf("%d%d%d",&opt,&u,&v);
if(opt==1)cut(u,v);
else if(opt==2)link(u,v);
else if(opt==3){
int d;scanf("%d",&d);
update(u,v,d);
}else query(u,v);
}
return 0;
}