题目描述
输入
输出
样例输入
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
样例输出
6/1
提示
对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=100 1<=U,V<=N
前三个操作都很简单了，LCT就能维护，重点是第四个操作。
求一个区间所有子区间的区间和之和，直接求所有区间和不好求，我们换一种角度去做。
考虑每个点对区间的贡献，假设当前区间是[l,r]，对于区间中的点k(l<=k<=r)，它的贡献就是它的点权*(k-l+1)*(r-k+1)。
那么我们维护区间答案，考虑怎么上传及修改？
先说上传，就是将一个点的左儿子区间+这个点+这个点的右儿子区间合并。
我们设size[x]为x子树大小，也就是x子树所代表的区间的长度；ls代表左子树，rs代表右子树。
对于左区间，每个点的贡献要加上它从左往右数的排名*它的点权*(1+size[rs])。
对于右区间，每个点的贡献要加上它从右往左数的排名*它的点权*(1+size[ls])。
对于点x要加上它的点权*(1+size[ls])*(1+size[rs])。
发现排名*点权的和无法直接求，因此还要维护两个信息lv[x],rv[x]，分别代表x子树所代表区间中每个点点权*从左/从右排名的和。
再看看这两个信息怎么合并，就以lv[x]为例吧，先将左右子节点的lv加上，左子树lv不变，右子树的lv发现每个点排名都加了(1+size[ls])，只要再加上右子树权值和*(1+size[ls])就好了。
综上所述，我们需要维护六个变量val,sum,lv,rv,size,ans，分别代表单点权值、子树权值和、点权*从左数排名之和、点权*从右数排名之和、子树节点数、区间所有子区间和之和即答案。
再说怎么修改？设n代表区间长,v为修改时的增量
val和sum比较常规在这就不说了。
lv和rv都加了
而ans则加了
最后这个推一个通项公式就好了。
知道怎么上传和修改后剩下的就LCT基本操作了。
但要注意翻转时也要把lv和rv交换且旋到原树根的操作splay之后不能只打标记，要先把当前点左右子树翻转，否则当前点的lv和rv是反的。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ls s[rt][0]
#define rs s[rt][1]
using namespace std;
int n,m;
int x,y;
int opt;
ll z;
int r[50010];
int s[50010][2];
int f[50010];
int st[50010];
ll lv[50010];
ll rv[50010];
ll sum[50010];
ll size[50010];
ll val[50010];
ll ans[50010];
ll a[50010];
ll p,q;
ll res;
int get(int rt)
{
return s[f[rt]][1]==rt;
}
int is_root(int rt)
{
return s[f[rt]][1]!=rt&&s[f[rt]][0]!=rt;
}
void add(int rt,ll v)
{
val[rt]+=v;
sum[rt]+=v*size[rt];
lv[rt]+=v*size[rt]*(size[rt]+1)/2;
rv[rt]+=v*size[rt]*(size[rt]+1)/2;
ans[rt]+=v*size[rt]*(size[rt]+1)*(size[rt]+2)/6;
a[rt]+=v;
}
void flip(int rt)
{
swap(ls,rs);
swap(lv[rt],rv[rt]);
r[rt]^=1;
}
void pushup(int rt)
{
size[rt]=size[ls]+size[rs]+1;
sum[rt]=sum[ls]+sum[rs]+val[rt];
lv[rt]=lv[ls]+lv[rs]+(val[rt]+sum[rs])*(size[ls]+1);
rv[rt]=rv[ls]+rv[rs]+(val[rt]+sum[ls])*(size[rs]+1);
ans[rt]=ans[ls]+ans[rs]+val[rt]*(size[ls]+1)*(size[rs]+1)+lv[ls]*(size[rs]+1)+rv[rs]*(size[ls]+1);
}
void pushdown(int rt)
{
if(r[rt])
{
r[rt]^=1;
flip(ls);
flip(rs);
}
if(a[rt])
{
add(ls,a[rt]);
add(rs,a[rt]);
a[rt]=0;
}
}
void rotate(int rt)
{
int fa=f[rt];
int anc=f[fa];
int k=get(rt);
if(!is_root(fa))
{
s[anc][get(fa)]=rt;
}
s[fa][k]=s[rt][k^1];
f[s[fa][k]]=fa;
s[rt][k^1]=fa;
f[fa]=rt;
f[rt]=anc;
pushup(fa);
pushup(rt);
}
void splay(int rt)
{
int top=0;
st[++top]=rt;
for(int i=rt;!is_root(i);i=f[i])
{
st[++top]=f[i];
}
for(int i=top;i>=1;i--)
{
pushdown(st[i]);
}
for(int fa;!is_root(rt);rotate(rt))
{
if(!is_root(fa=f[rt]))
{
rotate(get(fa)==get(rt)?fa:rt);
}
}
}
void access(int rt)
{
for(int x=0;rt;x=rt,rt=f[rt])
{
splay(rt);
s[rt][1]=x;
pushup(rt);
}
}
void reverse(int rt)
{
access(rt);
splay(rt);
flip(rt);
}
void link(int x,int y)
{
reverse(x);
f[x]=y;
}
void cut(int x,int y)
{
reverse(x);
access(y);
splay(y);
if(s[x][1]||f[x]!=y)
{
return ;
}
s[y][0]=f[x]=0;
pushup(y);
}
void change(int x,int y,ll z)
{
reverse(x);
access(y);
splay(y);
add(y,z);
}
int find(int rt)
{
while(f[rt])
{
rt=f[rt];
}
return rt;
}
void split(int x,int y)
{
reverse(x);
access(y);
splay(y);
}
ll gcd(ll x,ll y)
{
if(y==0)
{
return x;
}
return gcd(y,x%y);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&val[i]);
pushup(i);
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
link(x,y);
}
while(m--)
{
scanf("%d%d%d",&opt,&x,&y);
if(opt==1)
{
if(find(x)==find(y))
{
cut(x,y);
}
}
else if(opt==2)
{
if(find(x)!=find(y))
{
link(x,y);
}
}
else if(opt==3)
{
scanf("%lld",&z);
if(find(x)==find(y))
{
split(x,y);
add(y,z);
}
}
else
{
if(find(x)==find(y))
{
split(x,y);
p=ans[y];
q=size[y]*(size[y]+1)/2;
res=gcd(p,q);
printf("%lld/%lld\n",p/res,q/res);
}
else
{
printf("-1\n");
}
}
}
}