HYSBZ - 1036 樹的統計Count

HYSBZ - 1036 樹的統計Coun

　　一棵樹上有n個節點，編号分别為1到n，每個節點都有一個權值w。我們将以下面的形式來要求你對這棵樹完成一些操作： I. CHANGE u t : 把結點u的權值改為t II. QMAX u v: 詢問從點u到點v的路徑上的節點的最大權值 III. QSUM u v: 詢問從點u到點v的路徑上的節點的權值和 注意：從點u到點v的路徑上的節點包括u和v本身

Input

　　輸入的第一行為一個整數n，表示節點的個數。接下來n – 1行，每行2個整數a和b，表示節點a和節點b之間有一條邊相連。接下來n行，每行一個整數，第i行的整數wi表示節點i的權值。接下來1行，為一個整數q，表示操作的總數。接下來q行，每行一個操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式給出。 對于100％的資料，保證1<=n<=30000，0<=q<=200000；中途操作中保證每個節點的權值w在-30000到30000之間。

Output

　　對于每個“QMAX”或者“QSUM”的操作，每行輸出一個整數表示要求輸出的結果。

題解：可以用樹鍊剖分來做，将其分解成線段，用線段樹來維護。輸入節點值的時候應該注意，數組對應得下标應該以新的編号為準，然後再建線段樹。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#define INF 0x3f3f3f3f
#define eps 1e-6
#define PI 3.1415926
#define mod 1000000009
#define base 2333
using namespace std;
typedef long long LL;
const int maxn = 3e4 + 10;
const int maxx = 1e3 + 10;
inline void splay(int &v) {
    v=0;char c=0;int p=1;
    while(c<'0' || c >'9'){if(c=='-')p=-1;c=getchar();}
    while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
    v*=p;
}
int n, a, b, q, len, cnt, x, y, head[maxn], dep[maxn], siz[maxn];
int fa[maxn], son[maxn], id[maxn], val[maxn], top[maxn];
struct node {
    int to, next;
} e[maxn<<1];

struct Tree {
    int l, r, m;
    int mx, sum;
} tr[maxn<<2];

void add(int from, int to) {
    e[len].to = to;
    e[len].next = head[from];
    head[from] = len++;
}

void dfs1(int u, int ff, int deep) {
    dep[u] = deep, fa[u] = ff;
    son[u] = 0, siz[u] = 1;
    for(int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if(v == ff) continue;
        dfs1(v, u, deep+1);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v])
            son[u] = v;
    }
}

void dfs2(int u, int tp) {
    top[u] = tp;
    id[u] = ++cnt;
    if(son[u]) dfs2(son[u], tp);
    for(int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

void PushUp(int id) {
    tr[id].mx = max(tr[id<<1].mx, tr[id<<1|1].mx);
    tr[id].sum = tr[id<<1].sum+tr[id<<1|1].sum;
}

void build(int id, int l, int r) {
    tr[id].l = l, tr[id].r = r;
    tr[id].m = (l+r)>>1;
    if(l == r)  tr[id].mx = tr[id].sum = val[l];
    else {
        build(id<<1, l, tr[id].m);
        build(id<<1|1, tr[id].m+1, r);
        PushUp(id);
    }
}

void update(int id, int l, int r, int v) {
    if(l <= tr[id].l && r >= tr[id].r)
        tr[id].mx = tr[id].sum = v;
    else {
        if(l <= tr[id].m) update(id<<1, l, r, v);
        if(r > tr[id].m) update(id<<1|1, l, r, v);
        PushUp(id);
    }
}

int Query_Max(int id, int l, int r) {
    if(l <= tr[id].l && r >= tr[id].r)
        return tr[id].mx;
    else {
        int mx1 = -INF, mx2 = -INF;
        if(l <= tr[id].m) mx1 = Query_Max(id<<1, l, r);
        if(r > tr[id].m) mx2 = Query_Max(id<<1|1, l, r);
        return max(mx1, mx2);
    }
}

int Query_Sum(int id, int l, int r) {
    if(l <= tr[id].l && r >= tr[id].r)
        return tr[id].sum;
    else {
        int sum1 = 0, sum2 = 0;
        if(l <= tr[id].m) sum1 = Query_Sum(id<<1, l, r);
        if(r > tr[id].m) sum2 = Query_Sum(id<<1|1, l, r);
        return sum1+sum2;
    }
}

int Find(int u, int v, int op) {
    int tp1 = top[u], tp2 = top[v], ans = 0;
    if(op) ans = -INF;
    while(tp1 != tp2) {
        if(dep[tp1] < dep[tp2]) {
            swap(tp1, tp2);
            swap(u, v);
        }
        if(op) ans = max(ans, Query_Max(1, id[tp1], id[u]));
        else ans += Query_Sum(1, id[tp1], id[u]);
        u = fa[tp1], tp1 = top[u];
    }
    if(dep[u] > dep[v])  swap(u, v);
    if(op) ans = max(ans, Query_Max(1, id[u], id[v]));
    else ans += Query_Sum(1, id[u], id[v]);
    return ans;
}

void solve() {
    splay(n);
    memset(head, -1, sizeof(head));
    len = 0, cnt = 0;
    for(int i = 1; i < n; i++) {
        splay(a), splay(b);
        add(a, b), add(b, a);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    for(int i = 1; i <= n; i++)
        splay(val[id[i]]);
    build(1, 1, n);
    splay(q);
    char str[10];
    while(q--) {
        scanf("%s", str);
        splay(x), splay(y);
        if(str[0] == 'C')
            update(1, id[x], id[x], y);
        else {
            int ans = 0;
            if(str[1] == 'M') ans = Find(x, y, 1);
            if(str[1] == 'S') ans = Find(x, y, 0);
            printf("%d\n", ans);
        }
    }
}

int main() {
    //srand(time(NULL));
    //freopen("kingdom.in","r",stdin);
    //freopen("kingdom.out","w",stdout);
    solve();
}