HDU 3966 题解（树链剖分维护点权）

题意：

给定个营地，营地i有个敌人，有条边将个营地连起来。总共有p个操作，I操作是在C1到C2的链上的每个营地都增加K个敌人；D操作是在C1到C2的链上的每个营地都减少K个敌人；Q操作是在C营地上有多少个敌人。

树链剖分模板题，树链剖分后，用线段树或者树状数组维护即可。

线段树写得有点丑，要改掉用cin的坏毛病。

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 50005;
long long a[MAXN], b[MAXN];
int w[MAXN], rk[MAXN];
int n, m, p;
struct sgm {
    int l, r;
    long long sum;
    long long lazy;
} sgmt[MAXN << 2];
inline void push_up ( int rt ) {
    sgmt[rt].sum = sgmt[rt << 1].sum + sgmt[rt << 1 | 1].sum;
}
void build ( int rt, int l, int r ) {
    sgmt[rt].l = l;
    sgmt[rt].r = r;
    sgmt[rt].lazy = 0;
    if ( l == r ) {
        sgmt[rt].sum = w[rk[l]];
        return;
    }
    int mid = ( l + r ) >> 1;
    build ( rt << 1, l, mid );
    build ( rt << 1 | 1, mid + 1, r );
    push_up ( rt );
}
void update ( int rt, int l, int r, long long c ) {
    if ( l <= sgmt[rt].l && sgmt[rt].r <= r ) {
        sgmt[rt].sum += c * ( sgmt[rt].r - sgmt[rt].l + 1 );
        sgmt[rt].lazy += c;
        return;
    }
    int mid = ( sgmt[rt].l + sgmt[rt].r ) >> 1;
    if ( l <= mid ) {
        update ( rt << 1, l, r, c );
    }
    if ( mid < r ) {
        update ( rt << 1 | 1, l, r, c );
    }
    push_up ( rt );
}
long long query ( int rt, int l, int r ) {
    if ( l <= sgmt[rt].l && sgmt[rt].r <= r ) {
        return sgmt[rt].sum;
    }
    long long ans = sgmt[rt].lazy * ( min ( sgmt[rt].r, r ) - max ( sgmt[rt].l, l ) + 1 );
    int mid = ( sgmt[rt].l + sgmt[rt].r ) >> 1;
    if ( l <= mid ) {
        ans += query ( rt << 1, l, r );
    }
    if ( mid < r ) {
        ans += query ( rt << 1 | 1, l, r );
    }
    return ans;
}
int Head[MAXN << 1], ver[MAXN << 1], nxt[MAXN << 1];
int E;
void addedge ( int u, int v ) {
    ver[E] = v;
    nxt[E] = Head[u];
    Head[u] = E++;
}
int cnt;
int son[MAXN], size[MAXN], d[MAXN], fa[MAXN], top[MAXN], id[MAXN];
void dfs1 ( int f, int u, int depth ) {
    size[u] = 1;
    son[u] = 0;
    d[u] = depth;
    fa[u] = f;
    for ( int i = Head[u]; ~i; i = nxt[i] ) {
        int v = ver[i];
        if ( v == f ) {
            continue;
        }
        dfs1 ( u, v, depth + 1 );
        size[u] += size[v];
        if ( size[v] > size[son[u]] ) {
            son[u] = v;
        }
    }
}
void dfs2 ( int f, int u ) {
    top[u] = f;
    id[u] = ++cnt;
    rk[cnt] = u;
    if ( !son[u] ) {
        return;
    }
    dfs2 ( f, son[u] );
    for ( int i = Head[u]; ~i; i = nxt[i] ) {
        int v = ver[i];
        if ( v == fa[u] || v == son[u] ) {
            continue;
        }
        dfs2 ( v, v );
    }
}
void pathadd ( int x, int y, int k ) {
    int fx = top[x], fy = top[y];
    while ( id[fx] != id[fy] ) {
        if ( d[fx] > d[fy] ) {
            update ( 1, id[fx], id[x], k );
            x = fa[fx];
            fx = top[x];
        } else {
            update ( 1, id[fy], id[y], k );
            y = fa[fy];
            fy = top[y];
        }
    }
    if ( id[x] > id[y] ) {
        update ( 1, id[y], id[x], k );
    } else {
        update ( 1, id[x], id[y], k );
    }
    return;
}
int x, y, k;
char s[10];
int main() {
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    ios::sync_with_stdio ( 0 );
    cin.tie ( 0 );
    cout.tie ( 0 );
    while ( cin >> n >> m >> p ) {
        E = 0;
        cnt = 0;
        memset ( Head, -1, sizeof ( Head ) );
        for ( int i = 1; i <= n; i++ ) {
            cin >> w[i];
        }
        for ( int i = 0; i < m; i++ ) {
            cin >> x >> y;
            addedge ( x, y );
            addedge ( y, x );
        }
        dfs1 ( 0, 1, 1 );
        dfs2 ( 1, 1 );
        build ( 1, 1, n );
        for ( int i = 0; i < p; i++ ) {
            cin >> s;
            switch ( s[0] ) {
                case 'I':
                    cin >> x >> y >> k;
                    pathadd ( x, y, k );
                    break;
                case 'D':
                    cin >> x >> y >> k;
                    pathadd ( x, y, -k );
                    break;
                case 'Q':
                    cin >> x;
                    cout << query ( 1, id[x], id[x] ) << endl;
                    break;
            }
        }
    }
    return 0;
}