题解：
树链剖分是显然的
问题在于求树链的并
比较简单的方法是
用线段树打标记覆盖，查询标记区间大小
Qlog^2n
代码：
#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define rint register int
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
const int N=3e5;
const int N1=N*;
const int INF=1e9;
int n,l,cnt,dfn[N],size[N],fa[N],top[N],son[N],head[N],dep[N];
struct re{
int a,b;
}a[N*];
void arr(int x,int y)
{
a[++l].a=head[x];
a[l].b=y;
head[x]=l;
}
void dfs(int x,int y)
{
fa[x]=y; size[x]=;
int u=head[x];
dep[x]=dep[y]+;
while (u)
{
int v=a[u].b;
if (v!=y)
{
dfs(v,x);
if (size[v]>size[son[x]]) son[x]=v;
size[x]+=size[v];
}
u=a[u].a;
}
}
void dfs2(int x,int y)
{
dfn[x]=++cnt; top[x]=y;
if (!son[x]) return;
dfs2(son[x],y);
int u=head[x];
while (u)
{
int v=a[u].b;
if (v!=fa[x]&&v!=son[x]) dfs2(v,v);
u=a[u].a;
}
}
struct sgt{ int sum[N1],sum1[N1],lazy[N1],lazy1[N1];
#define mid ((h+t)/2)
IL void clear()
{
lazy1[]=-; sum1[]=;
}
IL int query()
{
return sum1[];
}
IL void down(int x,int h,int t)
{
if (lazy[x])
{
sum[x*]+=(mid-h+)*lazy[x];
sum[x*+]+=(t-mid)*lazy[x];
lazy[x*]+=lazy[x]; lazy[x*+]+=lazy[x];
lazy[x]=;
}
if (lazy1[x])
{
lazy1[x*]=lazy1[x*+]=lazy1[x];
if (lazy1[x]==) sum1[x*]=sum[x*],sum1[x*+]=sum[x*+];
else sum1[x*]=sum1[x*+]=;
lazy1[x]=;
}
}
IL void updata(int x)
{
sum[x]=sum[x*]+sum[x*+];
sum1[x]=sum1[x*]+sum1[x*+];
}
void change(int x,int h,int t,int h1,int t1,int k)
{
if (h1<=h&&t<=t1)
{
lazy[x]+=k; sum[x]+=(t-h+)*k; return;
}
down(x,h,t);
if (h1<=mid) change(x*,h,mid,h1,t1,k);
if (mid<t1) change(x*+,mid+,t,h1,t1,k);
updata(x);
}
void push(int x,int h,int t,int h1,int t1)
{
if (h1<=h&&t<=t1)
{
lazy1[x]=; sum1[x]=sum[x]; return;
}
down(x,h,t);
if (h1<=mid) push(x*,h,mid,h1,t1);
if (mid<t1) push(x*+,mid+,t,h1,t1);
updata(x);
}
}S;
void change(int x,int y)
{
int kk=dfn[x];
S.change(,,n,kk,kk+size[x]-,y);
}
void query(int x,int y)
{
int f1=top[x],f2=top[y];
while (top[x]!=top[y])
{
if (dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
S.push(,,n,dfn[f1],dfn[x]);
x=fa[f1]; f1=top[x];
}
if (dep[x]<dep[y]) swap(x,y);
S.push(,,n,dfn[y],dfn[x]);
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
rep(i,,n-)
{
int x,y; cin>>x>>y;
arr(x,y); arr(y,x);
}
dfs(,);
dfs2(,);
int m;
cin>>m;
rep(i,,m)
{
int kk,x,y,p;
cin>>kk;
if (!kk)
{
cin>>x>>y;
change(x,y);
} else
{
cin>>p;
rep(j,,p)
{
cin>>x>>y;
query(x,y);
}
int ans=S.query();
if (ans<) ans+=<<;
cout<<ans<<endl;
S.clear();
}
}
return ;
}