HDU 3966 트 리 체인 분할

HDU 3966 제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=3966 제목: n 개 (< = 1e5) 병영 은 나무의 형식 으로 서로 연결 되 어 연통 도 를 구성한다.초기 각 병영 의 병 수 를 제시 하 다.그 다음 에 수정 작업 이 있 습 니 다. 즉, u - v 의 경로 (u, v 포함) 가 지나 가 는 병영 병 의 수량 이 모두 감소 하거나 특정한 값 을 증가 합 니 다.조회 조작 이 있 습 니 다. 병영 현재 병사 의 수 를 구 합 니 다.이 수량 을 출력 합 니 다.사고: 누 드 나무 사슬 분할.여러 가지 잘못 쓰다.쉬 운 곳: 1) solve 에 있 는 u = fa [tp1] 는 u = fa [u] 2 라 고 쓰 여 있 습 니 다. Solve 에 있 는 여러 가지 쉬 운 WA 라 고 쓰 여 있 는 곳: 1) solve 에 u = v 는 2) 라인 트 리 를 만 들 때 tree [o]. val = val [o]. val = val [tid [l] 이 아 닌 tree [o]. val] (새로운 지침 으로 가 리 켜 서 라인 트 리 의 이 점 이 도대체 어느 점 인지 알 아야 합 니 다) 3) 라인 트 리 가 업데이트 되 었 을 때 pushdown。 원본 코드:

#pragma comment(linker,"/STACK:100000000,100000000")
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 50000 + 5;
int tp[MAXN], fa[MAXN], num[MAXN], son[MAXN], dep[MAXN];
int id[MAXN], cnt, tid[MAXN];
vector<int>lin[MAXN];
void dfs1(int u, int f, int deep)
{
    num[u] = 1, fa[u] = f, son[u] = 0, dep[u] = deep;
    for(int i = 0 ; i < (int)lin[u].size() ; i++){
        int v = lin[u][i];
        if(v == f)  continue;
        dfs1(v, u, deep + 1);
        num[u] += num[v];
        if(num[son[u]] < num[v])    son[u] = v;
    }
}
void dfs2(int u, int f)
{
    id[u] = ++cnt;
    tid[cnt] = u;
    tp[u] = f;
    if(son[u])  dfs2(son[u], f);
    for(int i = 0 ; i < (int)lin[u].size() ; i++){
        int v = lin[u][i];
        if(v == fa[u] || v == son[u])   continue;
        dfs2(v, v);
    }
}
struct Tree
{
    int l, r, val;
    int add;
}tree[MAXN * 4];
int val[MAXN];
void build(int l, int r, int o)
{
    tree[o].l = l, tree[o].r = r, tree[o].add = 0, tree[o].val = 0;
    if(l == r){
        tree[o].val = val[tid[l]];
        return;
    }
    int mid = (l + r) / 2;
    if(mid >= l)    build(l, mid, o * 2);
    if(mid < r)     build(mid + 1, r, o * 2 + 1);
}
void push_down(int o)
{
    if(tree[o].add == 0)    return;
    tree[o * 2].add += tree[o].add;
    tree[o * 2 + 1].add += tree[o].add;
    tree[o].add = 0;
}
int query(int u, int o)
{
// printf("u = %d, o = %d
", u, o);
// printf("tree[o].l = %d, tree[o].r = %d
", tree[o].l, tree[o].r);
// system("pause");
    if(tree[o].l == tree[o].r && tree[o].l == u){
        return tree[o].add + tree[o].val;
    }
    int ans = 0;
    push_down(o);
    int mid = (tree[o].l + tree[o].r) / 2;
    if(mid >= u)    ans = query(u, o * 2);
    else    ans = query(u, o * 2 + 1);
    return ans;
}
void update(int l, int r, int val, int o)
{
// if(tree[o].r < l || tree[o].l > r) return;
// printf("l = %d, r = %d, val = %d, tree[o].l = %d, tree[o].r = %d, o = %d
", l, r, val, tree[o].l, tree[o].r, o);
// system("pause");
    if(tree[o].l >= l && tree[o].r <= r){
        tree[o].add += val;
        return;
    }
    push_down(o);
    int mid = (tree[o].l + tree[o].r) / 2;
    if(mid < l) update(l, r, val, o * 2 + 1);
    else if(mid >= r)  update(l, r, val, o * 2);
    else{
        update(l, r, val, o * 2);
        update(l, r, val, o * 2 + 1);
    }
}
void solve(int u, int v, int val)
{
    int tp1 = tp[u], tp2 = tp[v];
    while(tp1 != tp2){
        if(dep[tp1] < dep[tp2]) swap(tp1, tp2), swap(u, v);
        update(id[tp1], id[u], val, 1);
        u = fa[tp1];
        tp1 = tp[u];
    }
    if(dep[u] > dep[v]) swap(u, v);
    update(id[u], id[v], val, 1);
}
char op[1000];
int main()
{
    int n, m, q;
    while(scanf("%d%d%d", &n, &m, &q) != EOF){
        for(int i = 0 ; i <= n ; i++)   lin[i].clear();
        int u, v, w;
        for(int i = 1 ; i <= n ; i++)   scanf("%d", &val[i]);
        for(int i = 0 ; i < m ; i++){
            scanf("%d%d", &u, &v);
            lin[u].push_back(v);
            lin[v].push_back(u);
        }
        cnt = 0;
        dfs1(1, 0, 1);
        dfs2(1, 1);
        build(1, n, 1);
        while(q--){
            scanf("%s", op);
            if(op[0] == 'Q'){
                scanf("%d", &u);
// printf("first = %d, second = %d
", query(id[u], 1), val[id[u]]);
                printf("%d
", query(id[u], 1));
            }
            else{
                scanf("%d%d%d", &u, &v, &w);
                if(op[0] == 'D')    solve(u, v, -w);
                else    solve(u, v, w);
            }
        }
    }
    return 0;
}