3091: 城市旅行
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1454 Solved: 483
[Submit][Status][Discuss]
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
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
6/1
HINT
对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=100 1<=U,V<=N
Source
谜一般的翻转标记
大爷题解传送门：http://blog.csdn.net/popoqqq/article/details/40823659
与上一题不一样的是，每个点在链上的位置不一定，所以没法维护vi*i之类的东西，只能像那样记录lsum和rsum然后update的时候处理
本题的翻转标记必须立即生效，因为反转标记还会影响lsum和rsum
除了一开始就Link外，还可以保存图然后dfs只设置fa关系不用Link，然而并没有带来常数提升反而更慢了...
BZOJ 100题达成
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define pa t[x].fa
#define lc t[x].ch[0]
#define rc t[x].ch[1]
const int N=5e4+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} struct node{
int ch[],fa,rev;
ll add,lsum,rsum,sum,exp,w,size;
}t[N];
inline int wh(int x){return t[pa].ch[]==x;}
inline int isRoot(int x){return t[pa].ch[]!=x&&t[pa].ch[]!=x;}
inline void update(int x){
t[x].size=t[lc].size+t[rc].size+;
t[x].sum=t[lc].sum+t[rc].sum+t[x].w;
t[x].lsum=t[lc].lsum+t[x].w*(t[lc].size+)+t[rc].lsum+t[rc].sum*(t[lc].size+);
t[x].rsum=t[rc].rsum+t[x].w*(t[rc].size+)+t[lc].rsum+t[lc].sum*(t[rc].size+);
t[x].exp=t[lc].exp+t[rc].exp
+t[lc].lsum*(t[rc].size+)+t[rc].rsum*(t[lc].size+)
+t[x].w*(t[lc].size+)*(t[rc].size+);
}
inline ll cal1(ll x){return x*(x+)/;}
inline ll cal2(ll x){return x*(x+)*(x+)/;}
inline void paint(int x,ll d){
t[x].w+=d;
t[x].add+=d;
t[x].sum+=d*t[x].size;
t[x].lsum+=d*cal1(t[x].size);
t[x].rsum+=d*cal1(t[x].size);
t[x].exp+=d*cal2(t[x].size);
}
inline void rever(int x){
swap(lc,rc);
swap(t[x].lsum,t[x].rsum);
t[x].rev^=;
}
inline void pushDown(int x){
if(t[x].rev){
rever(lc);
rever(rc);//!!!!!
t[x].rev=;
}
if(t[x].add){
paint(lc,t[x].add);
paint(rc,t[x].add);
t[x].add=;
}
} inline void rotate(int x){
int f=t[x].fa,g=t[f].fa,c=wh(x);
if(!isRoot(f)) t[g].ch[wh(f)]=x;t[x].fa=g;
t[f].ch[c]=t[x].ch[c^];t[t[f].ch[c]].fa=f;
t[x].ch[c^]=f;t[f].fa=x;
update(f);update(x);
}
int st[N],top;
inline void splay(int x){
top=;st[++top]=x;
for(int i=x;!isRoot(i);i=t[i].fa) st[++top]=t[i].fa;
for(int i=top;i>=;i--) pushDown(st[i]); for(;!isRoot(x);rotate(x))
if(!isRoot(pa)) rotate(wh(x)==wh(pa)?pa:x);
} inline void Access(int x){
for(int y=;x;y=x,x=pa){
splay(x);
rc=y;
update(x);
}
}
inline void MakeR(int x){
Access(x);splay(x);
rever(x);
}
inline int FindR(int x){
Access(x);splay(x);
while(lc) x=lc;
return x;
}
inline void Link(int x,int y){
MakeR(x);
t[x].fa=y;
}
inline void Cut(int x,int y){
MakeR(x);Access(y);splay(y);
t[y].ch[]=t[x].fa=;
update(y);//!!!
}
inline void Add(int x,int y,int d){
if(FindR(x)!=FindR(y)) return;
MakeR(x);Access(y);splay(y);
paint(y,d);
}
inline ll gcd(ll a,ll b){return b==?a:gcd(b,a%b);}
inline void Que(int x,int y){
if(FindR(x)!=FindR(y)){puts("-1");return;}
MakeR(x);Access(y);splay(y);
ll a=t[y].exp,b=t[y].size*(t[y].size+)/;
ll g=gcd(a,b);//printf("Que %d %d %d\n",a,b,g);
printf("%lld/%lld\n",a/g,b/g);
}
int n,Q,a,op,x,y,d;
int main(){
n=read();Q=read();
for(int i=;i<=n;i++){
a=read();
t[i].size=;
t[i].w=t[i].lsum=t[i].rsum=t[i].sum=t[i].exp=a;
}
for(int i=;i<=n-;i++) x=read(),y=read(),Link(x,y);
while(Q--){
op=read();x=read();y=read();
if(op==) if(FindR(x)==FindR(y)) Cut(x,y);
if(op==) if(FindR(x)!=FindR(y)) Link(x,y);
if(op==) d=read(),Add(x,y,d);
if(op==) Que(x,y);
}
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define pa t[x].fa
#define lc t[x].ch[0]
#define rc t[x].ch[1]
const int N=5e4+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} struct node{
int ch[],fa,rev;
ll add,lsum,rsum,sum,exp,w,size;
}t[N];
inline int wh(int x){return t[pa].ch[]==x;}
inline int isRoot(int x){return t[pa].ch[]!=x&&t[pa].ch[]!=x;}
inline void update(int x){
t[x].size=t[lc].size+t[rc].size+;
t[x].sum=t[lc].sum+t[rc].sum+t[x].w;
t[x].lsum=t[lc].lsum+t[x].w*(t[lc].size+)+t[rc].lsum+t[rc].sum*(t[lc].size+);
t[x].rsum=t[rc].rsum+t[x].w*(t[rc].size+)+t[lc].rsum+t[lc].sum*(t[rc].size+);
t[x].exp=t[lc].exp+t[rc].exp
+t[lc].lsum*(t[rc].size+)+t[rc].rsum*(t[lc].size+)
+t[x].w*(t[lc].size+)*(t[rc].size+);
}
inline ll cal1(ll x){return x*(x+)/;}
inline ll cal2(ll x){return x*(x+)*(x+)/;}
inline void paint(int x,ll d){
t[x].w+=d;
t[x].add+=d;
t[x].sum+=d*t[x].size;
t[x].lsum+=d*cal1(t[x].size);
t[x].rsum+=d*cal1(t[x].size);
t[x].exp+=d*cal2(t[x].size);
}
inline void rever(int x){
swap(lc,rc);
swap(t[x].lsum,t[x].rsum);
t[x].rev^=;
}
inline void pushDown(int x){
if(t[x].rev){
rever(lc);
rever(rc);//!!!!!
t[x].rev=;
}
if(t[x].add){
paint(lc,t[x].add);
paint(rc,t[x].add);
t[x].add=;
}
} inline void rotate(int x){
int f=t[x].fa,g=t[f].fa,c=wh(x);
if(!isRoot(f)) t[g].ch[wh(f)]=x;t[x].fa=g;
t[f].ch[c]=t[x].ch[c^];t[t[f].ch[c]].fa=f;
t[x].ch[c^]=f;t[f].fa=x;
update(f);update(x);
}
int st[N],top;
inline void splay(int x){
top=;st[++top]=x;
for(int i=x;!isRoot(i);i=t[i].fa) st[++top]=t[i].fa;
for(int i=top;i>=;i--) pushDown(st[i]); for(;!isRoot(x);rotate(x))
if(!isRoot(pa)) rotate(wh(x)==wh(pa)?pa:x);
} inline void Access(int x){
for(int y=;x;y=x,x=pa){
splay(x);
rc=y;
update(x);
}
}
inline void MakeR(int x){
Access(x);splay(x);
rever(x);
}
inline int FindR(int x){
Access(x);splay(x);
while(lc) x=lc;
return x;
}
inline void Link(int x,int y){
MakeR(x);
t[x].fa=y;
}
inline void Cut(int x,int y){
MakeR(x);Access(y);splay(y);
t[y].ch[]=t[x].fa=;
update(y);//!!!
}
inline void Add(int x,int y,int d){
if(FindR(x)!=FindR(y)) return;
MakeR(x);Access(y);splay(y);
paint(y,d);
}
inline ll gcd(ll a,ll b){return b==?a:gcd(b,a%b);}
inline void Que(int x,int y){
if(FindR(x)!=FindR(y)){puts("-1");return;}
MakeR(x);Access(y);splay(y);
ll a=t[y].exp,b=t[y].size*(t[y].size+)/;
ll g=gcd(a,b);//printf("Que %d %d %d\n",a,b,g);
printf("%lld/%lld\n",a/g,b/g);
}
int n,Q,a,op,x,y,d; struct edge{
int v,ne;
}e[N<<];
int cnt,h[N];
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
}
inline void dfs(int u,int fa){
for(int i=h[u];i;i=e[i].ne)
if(e[i].v!=fa){
t[e[i].v].fa=u;
dfs(e[i].v,u);
}
}
int main(){
n=read();Q=read();
for(int i=;i<=n;i++){
a=read();
t[i].size=;
t[i].w=t[i].lsum=t[i].rsum=t[i].sum=t[i].exp=a;
}
for(int i=;i<=n-;i++) x=read(),y=read(),ins(x,y);
dfs(,);
while(Q--){
op=read();x=read();y=read();
if(op==) if(FindR(x)==FindR(y)) Cut(x,y);
if(op==) if(FindR(x)!=FindR(y)) Link(x,y);
if(op==) d=read(),Add(x,y,d);
if(op==) Que(x,y);
}
}