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
解题思路：
大爷比我讲得好到不知道哪里去了PoPoQQQ的博客
就是考虑一个点会被经过多少次*多少贡献，感觉这个好套路，线性求解不是问题，不会动态维护QAQ。
考虑一个点代表的子树信息内部处理完毕，处理左子树对右子树或右子树对左子树的影响，像分治的想法QAQ。
最后累计答案就累计左子树答案+右子树答案+自己答案+左对右答案+右对左答案就好了。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define ls ch[0]
#define rs ch[1]
typedef long long lnt;
const int N=;
struct trnt{
int ch[];
int fa;
int lzt;
int wgt;
lnt add;
lnt val;
lnt ans;
lnt sum;
lnt lsum;
lnt rsum;
bool anc;
}tr[N];
int n,m;
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void pushup(int spc)
{
if(!spc)
return ;
tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+;
tr[spc].sum=tr[lll].sum+tr[rrr].sum+tr[spc].val;
tr[spc].lsum=tr[lll].lsum+tr[rrr].lsum+tr[spc].val*(tr[lll].wgt+)+tr[rrr].sum*(tr[lll].wgt+);
tr[spc].rsum=tr[lll].rsum+tr[rrr].rsum+tr[spc].val*(tr[rrr].wgt+)+tr[lll].sum*(tr[rrr].wgt+);
tr[spc].ans=tr[lll].ans+tr[rrr].ans+tr[lll].lsum*(tr[rrr].wgt+)+tr[rrr].rsum*(tr[lll].wgt+)+tr[spc].val*(tr[lll].wgt+)*(tr[rrr].wgt+);
return ;
}
void Add(int spc,lnt v)
{
if(!spc)
return ;
tr[spc].add+=v;
tr[spc].val+=v;
tr[spc].sum+=v*tr[spc].wgt;
tr[spc].lsum+=v*(tr[spc].wgt)*(tr[spc].wgt+)/;
tr[spc].rsum+=v*(tr[spc].wgt)*(tr[spc].wgt+)/;
tr[spc].ans+=v*(tr[spc].wgt+)*(tr[spc].wgt+)*tr[spc].wgt/;
return ;
}
void trr(int spc)
{
if(!spc)
return ;
tr[spc].lzt^=;
std::swap(lll,rrr);
std::swap(tr[spc].lsum,tr[spc].rsum);
return ;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
trr(lll);
trr(rrr);
tr[spc].lzt=;
}
if(tr[spc].add)
{
Add(lll,tr[spc].add);
Add(rrr,tr[spc].add);
tr[spc].add=;
}
return ;
}
void recal(int spc)
{
if(!tr[spc].anc)
recal(tr[spc].fa);
pushdown(spc);
return ;
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
if(tr[f].anc)
{
tr[spc].anc=true;
tr[f].anc=false;
}else
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
pushup(f);
pushup(spc);
return ;
}
void splay(int spc)
{
recal(spc);
while(!tr[spc].anc)
{
int f=tr[spc].fa;
if(tr[f].anc)
{
rotate(spc);
return ;
}
if(whc(spc)^whc(f))
rotate(spc);
else
rotate(f);
rotate(spc);
}
return ;
}
void access(int spc)
{
int lst=;
while(spc)
{
splay(spc);
tr[rrr].anc=true;
tr[lst].anc=false;
rrr=lst;
pushup(spc);
lst=spc;
spc=tr[spc].fa;
}
return ;
}
void Mtr(int spc)
{
access(spc);
splay(spc);
trr(spc);
return ;
}
void split(int x,int y)
{
Mtr(x);
access(y);
splay(y);
return ;
}
bool together(int x,int y)
{
split(x,y);
while(tr[y].ls)
y=tr[y].ls;
return x==y;
}
void link(int x,int y)
{
split(x,y);
tr[x].fa=y;
return ;
}
void cut(int x,int y)
{
split(x,y);
tr[y].ls=;
tr[x].fa=;
tr[x].anc=true;
pushup(y);
return ;
}
lnt gcd(lnt a,lnt b)
{
if(!b)
return a;
return gcd(b,a%b);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%lld",&tr[i].val);
tr[i].anc=true;
pushup(i);
}
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
link(a,b);
}
while(m--)
{
int cmd;
scanf("%d",&cmd);
if(cmd==)
{
int u,v;
scanf("%d%d",&u,&v);
if(together(u,v))
cut(u,v);
}else if(cmd==)
{
int u,v;
scanf("%d%d",&u,&v);
if(!together(u,v))
link(u,v);
}else if(cmd==)
{
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
if(together(u,v))
Add(v,d);
}else{
int u,v;
scanf("%d%d",&u,&v);
if(!together(u,v))
printf("%d\n",-);
else{
lnt top=tr[v].ans;
lnt bot=(lnt)(tr[v].wgt)*(lnt)(tr[v].wgt+)/;
lnt c=gcd(top,bot);
top/=c,bot/=c;
printf("%lld/%lld\n",top,bot);
}
}
}
return ;
}