Description

Input

Output

Sample Input

4 5
1 3 2 5
1 2
1 3
2 4
4 2 4
1 2 4
2 3 4
3 1 4 1
4 1 4

Sample Output

16/3
6/1

HINT

?

對(duì)于所有數(shù)據(jù)滿足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=100 1<=U,V<=N

惡心的動(dòng)態(tài)樹上維護(hù)各種信息。 不難發(fā)現(xiàn)ans=ΣAi*i*(len-i+1)。 我們?cè)趕play樹上維護(hù)幾個(gè)值：
sumv=ΣAi*i*(len-i+1) lsum=ΣAi*i rsum=ΣAi*(len-i+1) sum=ΣAi 不難維護(hù)者幾個(gè)變量的關(guān)系，打懶標(biāo)記時(shí)快速算一下Σi*(len-i+1)和Σi就行了。 注意flip時(shí)要交換兩子樹的lsum和rsum。 #include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #define lc ch[x][0] #define rc ch[x][1] #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; const int BufferSize=1<<16; char buffer[BufferSize],*head,*tail; inline char Getchar() {if(head==tail) {int l=fread(buffer,1,BufferSize,stdin);tail=(head=buffer)+l;}return *head++; } inline int read() {int x=0,f=1;char c=Getchar();for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;for(;isdigit(c);c=Getchar()) x=x*10+c-'0';return x*f; } typedef long long ll; const int maxn=50010; ll f[maxn],sumv[maxn],sum[maxn],lsum[maxn],rsum[maxn],s[maxn],addv[maxn],val[maxn]; int pre[maxn],fa[maxn],ch[maxn][2],flip[maxn]; void Add(int x,ll v) {if(!v||!x) return;sumv[x]+=v*f[s[x]];lsum[x]+=v*(1+s[x])*s[x]/2;rsum[x]+=v*(1+s[x])*s[x]/2;sum[x]+=v*s[x]; } void maintain(int x) {if(!x) return;s[x]=s[lc]+s[rc]+1;sum[x]=sum[lc]+sum[rc]+val[x];sumv[x]=sumv[lc]+sumv[rc]+lsum[lc]*(s[rc]+1)+rsum[rc]*(s[lc]+1)+val[x]*(s[lc]+1)*(s[rc]+1);lsum[x]=lsum[lc]+lsum[rc]+val[x]*(s[lc]+1)+sum[rc]*(s[lc]+1);rsum[x]=rsum[rc]+rsum[lc]+val[x]*(s[rc]+1)+sum[lc]*(s[rc]+1);Add(x,addv[x]); } void pushdown(int x) {if(flip[x]) {swap(lc,rc);swap(lsum[lc],rsum[lc]);swap(lsum[rc],rsum[rc]);flip[lc]^=1;flip[rc]^=1;flip[x]=0;}if(addv[x]) {val[x]+=addv[x];addv[lc]+=addv[x];addv[rc]+=addv[x];Add(lc,addv[x]);Add(rc,addv[x]);addv[x]=0;} } void rotate(int x) {int y=pre[x],z=pre[y],d=ch[y][0]==x;ch[y][d^1]=ch[x][d];pre[ch[x][d]]=y;ch[z][ch[z][1]==y]=x;pre[x]=z;ch[x][d]=y;pre[y]=x;maintain(y); } int S[maxn],top; void splay(int x) {for(int i=x;i;i=pre[i]) S[++top]=i;if(top!=1) fa[x]=fa[S[top]],fa[S[top]]=0;while(top) pushdown(S[top--]);while(pre[x]) rotate(x);maintain(x); } void access(int x) {for(int y=0;x;x=fa[x]) {splay(x);pre[ch[x][1]]=0;fa[ch[x][1]]=x;ch[x][1]=y;pre[y]=x;maintain(y=x);} } void makeroot(int x) {access(x);splay(x);flip[x]^=1;maintain(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) {makeroot(x);fa[x]=y; } void cut(int x,int y) {makeroot(x);access(y);splay(y);if(s[y]==2) {pre[ch[y][0]]=0;ch[y][0]=0;maintain(y);} } ll gcd(ll x,ll y) {return !y?x:gcd(y,x%y);} void query(int x,int y) {makeroot(x);access(y);splay(y);ll len=s[y]-1;len=(len+1)*(len+2)/2;ll ans=sumv[y],t=gcd(len,ans);printf("%lld/%lld\n",ans/t,len/t); } void update(int x,int y,ll v) {makeroot(x);access(y);splay(y);addv[y]+=v;Add(y,v); } int main() {int n=read(),m=read();f[1]=1;rep(i,2,n) f[i]=f[i-1]+(ll)i*(i-1)/2+i; rep(i,1,n) val[i]=read();rep(i,1,n-1) link(read(),read());while(m--) {int t=read(),x=read(),y=read();if(t==1) if(find(x)==find(y)) cut(x,y);if(t==2) if(find(x)!=find(y)) link(x,y);if(t==3) {ll v=read();if(find(x)==find(y)) update(x,y,v);}if(t==4) {if(find(x)==find(y)) query(x,y);else puts("-1");}}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/wzj-is-a-juruo/p/5208038.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3091: 城市旅行的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。