题目大意：
给定所有点的权值都为0，给定一棵树以后，每次询问都要求给定两点 x ， y 和一个权值w，要求x，y路径上所有点权值加上w，最后求出每一个节点的值
这里因为查询和点都特别多，所以希望能最后一次性更新节点的值
我们可以这么考虑，每次询问中找到x，y的最近公共祖先，那么我们将val[x] +=w , val[y]+=w , val[lca]-=w;
最后做dfs的时候，不断自底向上更新val值，让父亲加上所有儿子的val值，那么lca减掉了一个w，最后2端会加上两个w，最后还是相当于加了一个w
但是因为lca加了一个w，那么会影响更上面的祖先，所以我们在考虑将 val[father[lca]]-=w , 这样加上lca传上来的w就相互抵消了，再之后的祖先就不会影响了
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 #define N 50100 7 int fa[N] , father[N]; 8 9 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} 10 int first[N] , k; 11 struct Edge{ 12 int y , next; 13 }e[N<<1]; 14 15 void add_edge(int x , int y) 16 { 17 e[k].y = y , e[k].next = first[x]; 18 first[x] = k++; 19 } 20 21 int _first[N] , _k; 22 struct QEdege{ 23 int y , next , w , lca; 24 }qe[N<<1]; 25 26 void add_que_edge(int x , int y , int w) 27 { 28 qe[_k].y = y , qe[_k].next = _first[x] , qe[_k].w = w , qe[_k].lca=0; 29 _first[x] = _k++; 30 } 31 bool vis[N]; 32 33 void tarjan(int u , int f) 34 { 35 vis[u] = true , fa[u]=u , father[u] = f; 36 for(int i=first[u] ; ~i ; i=e[i].next){ 37 int v = e[i].y; 38 if(vis[v]) continue; 39 tarjan(v , u); 40 fa[v] = u; 41 } 42 for(int i=_first[u] ; ~i ; i=qe[i].next){ 43 int v = qe[i].y; 44 if(vis[v]){ 45 int lca = find(v); 46 qe[i].lca = qe[i^1].lca = lca; 47 } 48 } 49 } 50 51 int val[N] , n , m; 52 53 void dfs(int u , int f) 54 { 55 for(int i=first[u] ; ~i ; i=e[i].next){ 56 int v = e[i].y; 57 if(v == f) continue; 58 dfs(v , u); 59 val[u] += val[v]; 60 } 61 } 62 63 int main() 64 { 65 // freopen("in.txt" , "r" , stdin); 66 int cas , x , y , w; 67 scanf("%d" , &cas); 68 for(int i=1 ; i<=cas ; i++){ 69 scanf("%d" , &n); 70 memset(first , -1 , sizeof(first)); 71 k=0; 72 memset(_first , -1 , sizeof(_first)); 73 _k=0; 74 for(int j=1 ; j<n ; j++){ 75 scanf("%d%d" , &x , &y); 76 x++ , y++; 77 add_edge(x , y); 78 add_edge(y , x); 79 } 80 scanf("%d" , &m); 81 for(int j=0 ; j<m ; j++){ 82 scanf("%d%d%d" , &x , &y , &w); 83 x++ , y++; 84 add_que_edge(x , y , w); 85 add_que_edge(y , x , w); 86 } 87 memset(vis , 0 , sizeof(vis)); 88 tarjan(1 , 1); 89 memset(val , 0 , sizeof(val)); 90 for(int j=0 ; j<_k ; j+=2){ 91 val[qe[j].lca] -= qe[j].w; 92 if(qe[j].lca!=father[qe[j].lca]) val[father[qe[j].lca]] -= qe[j].w; 93 val[qe[j].y] += qe[j].w , val[qe[j^1].y] += qe[j].w; 94 // cout<<j<<" "<<qe[j].y<<" "<<qe[j^1].y<<" "<<qe[j].w<<" "<<qe[j].lca<<" "<<fa[qe[j].lca]<<endl; 95 } 96 dfs(1 , 0); 97 printf("Case #%d: " , i); 98 for(int j=1 ; j<=n ; j++) printf("%d " , val[j]); 99 } 100 return 0; 101 }