题目
题目描述
乐乐做了个梦，梦见自己当了国王。乐乐王国有N座城市（编号从1~N，首都的编号为1）。乐乐王国的道路构成树状结构：首都1与几个大城市相连，这几个大城市又通过道路与一些稍小的城市相连……严格地说，这N座城市构成一棵有根树（1为树根），城市i的管理区域为以i为根的子树。
道路都是双向的。经过每条道路需要收费，从城市A到城市B的花费为A到B的简单路径上所有道路的费用之和（不妨称之为城市对(A, B)之间的花费）。显然，一棵树上任意两点之间的简单路径（即不能重复经过某个点的路径）是唯一的。
由于物价飞涨，经过一番缜密的思考，乐乐决定重新规划自己国家的道路收费。具体来说，他要进行Q个操作，每个操作是如下两种类型：
INC u v w——表示u到v的路径上，所有的道路的收费增加w；
ASK p——表示询问城市p的管理区域中，所有的“城市对”的花费之和。比如，城市p的管理区域（即以p为根子树）中有城市c1, c2, c3, …，cs（这里面包括p），询问所有的城市对(c1, c2), (c1, c3), …, (c2, c3), …,(cs-1, cs)的花费之和。
乐乐把这个问题交给你，快帮帮他吧！
输入描述:
第一行输入两个正整数N，Q，分别表示城市的数目和操作的数目。
接下来有N – 1行，第i行是两个正整数pi, ci，表示城市pi是城市i的父亲结点，且连接pi和i的道路的初始收费为ci（1≤ci≤1000）。
接下来有Q行，每行是如下两种类型之一：
INC u v w (u, v, w都是整数，且1≤u, v≤N, 0≤w≤1000，注意u, v可能相等)
ASK p (p是正整数，且p≤N)
意义如题目所述。
输出描述:
对每个ASK类型的操作，输出所求的答案。请你输出答案对2019取模后的结果。
示例1
输入
5 5
1 1
2 5
1 2
2 1
INC 2 4 2
INC 3 4 1
ASK 2
INC 2 5 3
ASK 1
输出
14
84
说明
乐乐王国的地图如下：
经过前两次操作，道路费用变化如图2。
这时，(2,3),(2,5),(3,5)的费用和=6+1+7=14。
再进行一次修改（第4个操作），变化如图3。
这时，(1,2)(1,3)(1,4)(1,5)(2,3)(2,4)(2,5)(3,4)(3,5)(4,5)的总费用为：
4+10+5+8+6+9+4+15+10+13=84
备注
1≤Q,N≤50000，树的深度不超过10000，其他输入数据的范围在输入格式中已给出。
题解
难点是操作二的维护
发现对于子树$a$，子树里一条边$(u,v,dis)$，产生的贡献是$dis\times(size_a-size_v)\times size_v$
发现$size_a$很难维护，所以可以维护$ans=\sum_{i\in a}dis_i\times size_{v_i}$和$ans’=\sum_{i\in a}dis_i\times size_{v_i}^2$，询问$a$的时候返回$size_a\times ans-ans’$，用树剖维护即可
代码
# include<bits/stdc++.h>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=5e4+5,mod=2019;
struct p{
LL siz1,siz2,ans,ans1,lazy;
}s[MAX<<2];
struct o{
int fr,x,y,dis;
}c[MAX<<1];
int n,q,num,cnt;
int h[MAX],d[MAX],siz[MAX],son[MAX],f[MAX],top[MAX],id[MAX],w[MAX],Siz2[MAX];
char ss[12];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x)
{
int y=read(),dis=read();
c[++num]=(o){x,h[x],y,dis},h[x]=num;
c[++num]=(o){y,h[y],x,dis},h[y]=num;
}
void dfs(int x,int fa=0)
{
d[x]=d[fa]+1,f[x]=fa,siz[x]=1;
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=fa)
{
dfs(c[i].y,x),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
}
}
void dfs1(int x,int tp=1)
{
top[x]=tp,id[x]=++cnt;
if(!son[x]) return;
dfs1(son[x],tp);
for(int i=h[x];i;i=c[i].x)
if(c[i].y!=f[x]&&c[i].y!=son[x]) dfs1(c[i].y,c[i].y);
}
void pus(int k)
{
s[k].siz1=(s[tl].siz1+s[tr].siz1)%mod;
s[k].siz2=(s[tl].siz2+s[tr].siz2)%mod;
s[k].ans=(s[tl].ans+s[tr].ans)%mod;
s[k].ans1=(s[tl].ans1+s[tr].ans1)%mod;
}
void build(int l=1,int r=n,int k=1)
{
if(l==r) return void(s[k]=(p){1ll*Siz2[l]*Siz2[l]%mod,Siz2[l],1ll*w[l]*Siz2[l]%mod,1ll*w[l]*Siz2[l]*Siz2[l]%mod});
build(l,mid,tl),build(mid+1,r,tr),pus(k);
}
void down(int k)
{
if(!s[k].lazy) return;
int f=s[k].lazy;
s[tl].ans=(s[tl].ans+1ll*f*s[tl].siz2)%mod,s[tr].ans=(s[tr].ans+1ll*f*s[tr].siz2)%mod;
s[tl].ans1=(s[tl].ans1+1ll*f*s[tl].siz1)%mod,s[tr].ans1=(s[tr].ans1+1ll*f*s[tr].siz1)%mod;
s[k].lazy=0,s[tl].lazy=(s[tl].lazy+f)%mod,s[tr].lazy=(s[tr].lazy+f)%mod;
}
void change(int l,int r,int k,int L,int R,int dis)
{
if(l==L&&r==R)
{
s[k].lazy=(s[k].lazy+dis)%mod,s[k].ans1=(s[k].ans1+1ll*s[k].siz1*dis%mod)%mod;
return void(s[k].ans=(s[k].ans+1ll*s[k].siz2*dis%mod)%mod);
}
down(k);
if(R<=mid) change(l,mid,tl,L,R,dis);
else if(L>mid) change(mid+1,r,tr,L,R,dis);
else change(l,mid,tl,L,mid,dis),change(mid+1,r,tr,mid+1,R,dis);
pus(k);
}
void CHANGE(int x,int y,int dis)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
change(1,n,1,id[top[x]],id[x],dis),x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
if(x!=y) change(1,n,1,id[x]+1,id[y],dis);
}
int ask(int l,int r,int k,int L,int R,int rt)
{
if(L>R||R>n) return 0;
if(l==L&&r==R) return (1ll*s[k].ans*siz[rt]-s[k].ans1)%mod;
down(k);
if(R<=mid) return ask(l,mid,tl,L,R,rt);
if(L>mid) return ask(mid+1,r,tr,L,R,rt);
return (ask(l,mid,tl,L,mid,rt)+ask(mid+1,r,tr,mid+1,R,rt))%mod;
}
int main()
{
n=read(),q=read();
for(int i=1;i<n;add(++i));
dfs(1),dfs1(1);
for(int i=1;i<=num;i+=2)
{
int x=c[i].fr,y=c[i].y;
if(d[x]>d[y]) swap(x,y);
Siz2[id[y]]=siz[y],w[id[y]]=c[i].dis%mod;
}
build();
for(int i=1,x,y;i<=q;++i)
{
scanf("%s",ss),x=read();
if(ss[0]=='I') y=read(),CHANGE(x,y,read());
else if(ss[0]=='A') printf("%d\n",(ask(1,n,1,id[x]+1,id[x]+siz[x]-1,x)+mod)%mod);
}
return 0;
}
