题意：给一棵树，两种操作： ADD1: 给u-v路径上所有点加上值k， ADD2：给u-v路径上所有边加上k，初始值都为0，问最后每个点和每条边的值，输出。
解法：树链剖分可做，剖出来如果直接用线段树来区间更新的话会TLE，所以要换一种姿势，有一种树链剖分的经典姿势就是看做树状数组一样，每次加值的时候，比如u->v之间加一个值k，那么在u处+k,v+1处-k即可，然后扫一遍，每次把当前位置要做的操作做完，此时总共加的值就是当前处的值，扫一遍的时候维护的是前缀的和，也就是两个ans不清零。
这题卡时间太紧，不加读入挂会T，不加输出挂的话跑4921ms，也是飘过，加了输入输出挂才稍微好点，4687ms，可能是树链剖分不够优越
代码：
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define lll __int64
using namespace std;
#define N 100007 int siz[N]; //子树大小
int son[N]; //重儿子
int dep[N]; //深度
int pos[N],apos[N]; //点在线段树中的位置
int Top[N]; //所在重链的祖先
int fa[N]; //父节点
lll eans[N],nans[N]; //答案
int head[*N],tot,POS,n,m;
struct Edge
{
int v,next;
}G[*N],Qe[*N],Qn[*N];
int heade[*N],headn[*N],tote,totn;
struct node
{
int u,v;
}edge[N]; void init()
{
POS = tot = tote = totn = ;
memset(head,-,sizeof(head));
memset(son,-,sizeof(son));
memset(heade,-,sizeof(heade));
memset(headn,-,sizeof(headn));
} void addedge(int u,int v)
{
G[tot].v = v, G[tot].next = head[u], head[u] = tot++;
G[tot].v = u, G[tot].next = head[v], head[v] = tot++;
} void ADDNedge(int u,int v) //代替vector来存操作
{
Qn[totn].v = v, Qn[totn].next = headn[u], headn[u] = totn++;
} void ADDEedge(int u,int v) //代替vector来存操作
{
Qe[tote].v = v, Qe[tote].next = heade[u], heade[u] = tote++;
} void dfs(int u,int f)
{
dep[u] = dep[f]+;
siz[u] = ;
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(v == f) continue;
fa[v] = u;
dfs(v,u);
if(son[u] == - || siz[v] > siz[son[u]]) son[u] = v;
siz[u] += siz[v];
}
} void dfs2(int u,int top)
{
pos[u] = ++POS;
apos[POS] = u;
Top[u] = top;
if(son[u] != -) dfs2(son[u],top);
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(v != fa[u] && v != son[u])
dfs2(v,v);
}
} void AddEdge(int u,int v,int k)
{
int fx = Top[u], fy = Top[v];
while(fx != fy)
{
if(dep[fx] < dep[fy])
{
swap(u,v);
swap(fx,fy);
}
ADDEedge(pos[fx],k);
ADDEedge(pos[u]+,-k);
u = fa[fx];
fx = Top[u];
}
if(dep[u] > dep[v]) swap(u,v);
ADDEedge(pos[son[u]],k);
ADDEedge(pos[v]+,-k);
} void AddNode(int u,int v,int k)
{
int fx = Top[u], fy = Top[v];
while(fx != fy)
{
if(dep[fx] < dep[fy])
{
swap(u,v);
swap(fx,fy);
}
ADDNedge(pos[fx],k);
ADDNedge(pos[u]+,-k);
u = fa[fx];
fx = Top[u];
}
if(dep[u] > dep[v]) swap(u,v);
ADDNedge(pos[u],k);
ADDNedge(pos[v]+,-k);
} inline int in()
{
char ch;
int a = ;
while((ch = getchar()) == ' ' || ch == '\n');
a += ch - '';
while((ch = getchar()) != ' ' && ch != '\n')
{
a *= ;
a += ch - '';
}
return a;
} inline void out(lll num){
bool flag=false;
if(num<){
putchar('-');
num=-num;
}
int ans[],top=;
while(num!=){
ans[top++]=num%;
num/=;
}
if(top==)
putchar('');
for(int i=top-;i>=;i--){
char ch=ans[i]+'';
putchar(ch);
}
} int main()
{
int u,v,k,i,j,t,cs = ;
char ss[];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(i=;i<n;i++)
{
edge[i].u = in();
edge[i].v = in();
addedge(edge[i].u,edge[i].v);
}
dep[] = ;
dfs(,);
dfs2(,);
while(m--)
{
scanf("%s",ss);
u = in(), v = in(), k = in();
if(ss[] == '') //node
AddNode(u,v,k);
else
AddEdge(u,v,k);
}
printf("Case #%d:\n",cs++);
lll ansedge = ,ansnode = ;
for(i=;i<=n;i++)
{
for(j=headn[i];j!=-;j=Qn[j].next)
ansnode += Qn[j].v;
for(j=heade[i];j!=-;j=Qe[j].next)
ansedge += Qe[j].v;
nans[apos[i]] = ansnode;
eans[apos[i]] = ansedge;
}
for(i=;i<=n;i++)
{
out(nans[i]);
printf("%c",i==n?'\n':' ');
}
for(i=;i<n;i++)
{
int u = edge[i].u, v = edge[i].v;
if(dep[u] > dep[v]) swap(u,v);
out(eans[v]);
printf("%c",i==n-?'\n':' ');
}
if(n == ) puts(""); //PE..
}
return ;
}