UVA 1674 Lightning Energy Report (树链剖分)

题意：

给你一颗树（节点数最多5w）， 给你q个操作，  每个操作，让你u，v两个结点之间的路径上的所有的点的权值都加上w。最后输出n 个点的权值？

思路：

裸树链剖分= =~

和HDU 3966 一样的， 用树状数组就可以了

详细见那一篇博客：Blog_HDU 3966

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define ps push_back#define Siz(x) (int)x.size()using namespace std;const int maxn = 50000 + 7;int T, n, q, id, ks;int fa[maxn], son[maxn], num[maxn], p[maxn], fp[maxn], top[maxn], c[maxn], deep[maxn];vector<int>g[maxn];int lowbit(int x){    return x&-x;}int sum(int i){    int ans = 0;    while(i){        ans += c[i];        i -= lowbit(i);    }    return ans;}void add(int i,int val){    while(i <= n){        c[i] += val;        i += lowbit(i);    }}void init(){    id = 1;    for (int i = 0; i < n; ++i)g[i].clear();    memset(son,-1,sizeof son);    memset(c,0,sizeof c);}void dfs(int cur,int f,int dep){    fa[cur] = f;    num[cur] = 1;    deep[cur] = dep;    for (int i = 0; i < Siz(g[cur]); ++i){        int v = g[cur][i];        if (v != f){            dfs(v,cur,dep+1);            if (son[cur] == -1 || num[v] > num[cur]){                son[cur] = v;                num[cur] = 1 + num[v];            }        }    }}void link(int cur,int tp){    p[cur] = id++;    fp[id-1] = cur;    top[cur] = tp;    if (son[cur] == -1) return;    link(son[cur],tp);    for (int i = 0; i < Siz(g[cur]); ++i){        int v = g[cur][i];        if (v != fa[cur] && v != son[cur]) link(v,v);    }}void deal(int u,int v,int w){    int fu = top[u], fv = top[v];    while(fu != fv){        if (deep[fu] < deep[fv]){            swap(fu,fv);            swap(u,v);        }        add(p[fu],w); add(p[u]+1,-w);        u = fa[fu];        fu = top[u];    }    if (deep[u] < deep[v]) swap(u,v);    add(p[u]+1,-w);    add(p[v],w);}int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        init();        for (int i = 1; i < n; ++i){            int u,v;            scanf("%d %d",&u, &v);            g[u].ps(v);            g[v].ps(u);        }        dfs(0,0,0);        link(0,0);        int q;        scanf("%d",&q);        while(q--){            int u,v,w;            scanf("%d %d %d",&u, &v, &w);            deal(u,v,w);        }        PRintf("Case #%d:/n",++ks);        for (int i = 0; i < n; ++i) printf("%d/n",sum(p[i]));    }    return 0;}