【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=3091
【思路】
膜Popoqqq大爷的题解 click here
【代码】是坑。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
using namespace std; typedef long long ll;
const int N = 4e5+; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} namespace LCT { struct Node {
Node *ch[],*fa;
ll v,add,rev,ans,sum,ls,rs,siz;
Node() ;
void addv(ll x) {
add+=x;
v+=x;
sum+=siz*x;
ls+=x*siz*(siz+)/;
rs+=x*siz*(siz+)/;
ans+=x*siz*(siz+)*(siz+)/;
}
void reverse() {
rev^=;
swap(ls,rs);
swap(ch[],ch[]);
}
void up_push() {
if(fa->ch[]==this||fa->ch[]==this)
fa->up_push();
if(rev) {
ch[]->reverse();
ch[]->reverse();
rev=;
}
if(add) {
ch[]->addv(add);
ch[]->addv(add);
add=;
}
}
void maintain() {
siz=ch[]->siz+ch[]->siz+;
sum=ch[]->sum+ch[]->sum+v;
ls=ch[]->ls+v*(ch[]->siz+)+ch[]->ls+ch[]->sum*(ch[]->siz+);
rs=ch[]->rs+v*(ch[]->siz+)+ch[]->rs+ch[]->sum*(ch[]->siz+);
ans=ch[]->ans+ch[]->ans+(ch[]->siz+)*ch[]->ls+(ch[]->siz+)*ch[]->rs
+(ch[]->siz+)*(ch[]->siz+)*v;
}
} *null=new Node, T[N];
Node::Node() {
ch[]=ch[]=fa=null;
v=rev=add=ans=sum=ls=rs=;
siz=;
}
void rot(Node* o,int d) {
Node* p=o->fa;
p->ch[d]=o->ch[d^];
o->ch[d^]->fa=p;
o->ch[d^]=p;
o->fa=p->fa;
if(p==p->fa->ch[])
p->fa->ch[]=o;
else if(p==p->fa->ch[])
p->fa->ch[]=o;
p->fa=o;
p->maintain();
}
void splay(Node* o) {
o->up_push();
Node *nf,*nff;
while(o->fa->ch[]==o||o->fa->ch[]==o) {
nf=o->fa,nff=nf->fa;
if(o==nf->ch[]) {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
} else {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
}
}
o->maintain();
}
void Access(Node* o) {
Node* son=null;
while(o!=null) {
splay(o);
o->ch[]=son;
o->maintain();
son=o; o=o->fa;
}
}
void evert(Node* o) {
Access(o);
splay(o);
o->reverse();
}
void Link(Node* u,Node* v) {
evert(u);
u->fa=v;
}
void Cut(Node* u,Node* v) {
evert(u);
Access(v),splay(v);
v->ch[]=u->fa=null;
v->maintain();
}
Node* find(Node* o) {
while(o->fa!=null) o=o->fa;
return o;
} }
using namespace LCT; struct Edge { int v,nxt;
}e[N<<];
int en=,front[N];
void adde(int u,int v)
{
e[++en]=(Edge){v,front[u]}; front[u]=en;
} int n,m; void build(int u,int fa)
{
trav(u,i) {
int v=e[i].v;
if(v!=fa) {
T[v].fa=&T[u];
build(v,u);
}
}
}
ll gcd(ll a,ll b)
{
return b? gcd(b,a%b):a;
} int main()
{
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
null->siz=;
scanf("%d%d",&n,&m);
FOR(i,,n) {
ll x;
scanf("%lld",&x);
T[i].v=T[i].sum=T[i].ls=T[i].rs=T[i].ans=x;
}
int op,u,v; ll d;
FOR(i,,n-) {
scanf("%d%d",&u,&v);
adde(u,v),adde(v,u);
}
build(,-);
FOR(i,,m) {
scanf("%d%d%%d",&op,&u,&v);
if(op==) {
if(find(&T[u])==find(&T[v]))
Cut(&T[u],&T[v]);
} else
if(op==) {
if(find(&T[u])!=find(&T[v]))
Link(&T[u],&T[v]);
} else
if(op==) {
if(find(&T[u])==find(&T[v])) {
scanf("%lld",&d);
evert(&T[u]);
Access(&T[v]),splay(&T[v]);
T[v].addv(d);
}
} else {
if(find(&T[u])!=find(&T[v])) puts("-1");
else {
evert(&T[u]);
Access(&T[v]),splay(&T[v]);
ll x=T[v].ans,y=T[v].siz*(T[v].siz+)>>;
ll g=gcd(x,y);
printf("%lld/%lld\n",x/g,y/g);
}
}
}
return ;
}