Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2968 Accepted Submission(s): 507
题意：
先给你一颗树，然后有两种操作：
● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.
● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.
add1把从u到v的点所经过的点的权值都增加k；
add2把从u到v所经过的边都增加k；
大婶们都说，这是树链剖分的水题。。。
我用邻接表搞了很久很久，却还是wa。。。。
邻接表代码先贴着，有空学学数链剖分。。。
wa代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
const int MAXN=1e5+10;
int head[MAXN<<1];
int edgnum;
struct Edge{
int from,to,next,val;
};
Edge edg[MAXN<<1];
struct Node{
int u,v;
};
Node dt[MAXN];
int dis[MAXN];
void initial(){
mem(head,-1);edgnum=0;mem(dis,0);
}
void add(int u,int v,int w){
Edge E={u,v,head[u],w};
edg[edgnum]=E;
head[u]=edgnum++;
}
/*void adw(int u,int v,int w){
for(int i=head[u];i!=-1;i=edg[i].next){
}
}*/
void dfs1(int i,int v,int w){
// printf("%d\n",i);
if(i==-1)return;
edg[i].val+=w;
for(int j=head[v];j!=-1;j=edg[j].next){
if(edg[j].to==edg[i].from){
edg[j].val+=w;break;
}
}
// printf("%d %d\n",edg[i].from,edg[i].to);
if(edg[i].to==v)return;
dfs1(head[edg[i].to],v,w);
}
void dfs2(int i,int v,int w){
if(i==-1)return;
int to=edg[i].to;
dis[to]+=w;
// printf("%d\n",to);
if(edg[i].to==v)return;
dfs2(head[edg[i].to],v,w);
}
int main()
{
int t,n,m,kase=0;
char s[5];
scanf("%d",&t);
while(t--){
int u,v,w;
initial();
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
scanf("%d%d",&dt[i].u,&dt[i].v);
add(dt[i].u,dt[i].v,0);
add(dt[i].v,dt[i].u,0);
}
while(m--){
scanf("%s",s);
scanf("%d%d%d",&u,&v,&w);
if(strcmp(s,"ADD1")==0){
dis[u]+=w;
if(u!=v)dfs2(head[u],v,w);
}
else{
if(u!=v)dfs1(head[u],v,w);
}
}
printf("Case #%d:\n",++kase);
for(int i=1;i<=n;i++){
if(i!=1)printf(" ");
printf("%d",dis[i]);
}puts("");
for(int i=1;i<n;i++){
u=dt[i].u;v=dt[i].v;
int k=head[u];
if(i!=1)printf(" ");
printf("%d",edg[k].val);
}puts("");
}
return 0;
}
原文：http://www.cnblogs.com/handsomecui/p/5023935.html