【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1036

【题意】

【题解】



树链剖分入门题;

每一条链维护一个线段树就好;

uppest数组维护这条链的最顶端的元素;

一条链一条链的往上走;直到两个点在同一条链里面了

balabala



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 3e4+100;

const int INF = 3e4 + 200;

int n,fa[N],siz[N],dep[N],uppest[N],bh[N],cnt;

int v[N],sum[N<<2],mx[N<<2];

vector <int> G[N];

void in()

{

    rei(n);

    rep1(i, 1, n - 1)

    {

        int x, y;

        rei(x), rei(y);

        G[x].pb(y), G[y].pb(x);

    }

    rep1(i, 1, n)

        rei(v[i]);

}

void dfs1(int x)

{

    int len = G[x].size();

    siz[x] = 1;

    rep1(i, 0, len - 1)

    {

        int y = G[x][i];

        if (y == fa[x]) continue;

        fa[y] = x;

        dep[y] = dep[x] + 1;

        dfs1(y);

        siz[x] += siz[y];

    }

}

void dfs2(int x, int chain)

{

    int len = G[x].size();

    int k = 0;

    bh[x] = ++cnt;

    uppest[x] = chain;

    rep1(i, 0, len - 1)

    {

        int y = G[x][i];

        if (dep[y]>dep[x] && siz[y] > siz[k])

            k = y;

    }

    if (k == 0) return;

    dfs2(k, chain);

    rep1(i, 0, len - 1)

    {

        int y = G[x][i];

        if (dep[y] > dep[x] && y != k)

            dfs2(y, y);

    }

}

void updata(int pos, int val,int l, int r, int rt)

{

    if (l == r)

    {

        sum[rt] = mx[rt] = val;

        return;

    }

    int m = (l + r) >> 1;

    if (pos <= m)

        updata(pos, val,lson);

    else

        updata(pos, val,rson);

    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];

    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);

}

int query_max(int L, int R, int l, int r, int rt)

{

    if (L <= l && r <= R)

        return mx[rt];

    int m = (l + r) >> 1;

    int temp1 = -INF;

    if (L <= m)

        temp1 = max(temp1, query_max(L, R, lson));

    if (m < R)

        temp1 = max(temp1, query_max(L, R, rson));

    return temp1;

}

int get_max(int u, int v)

{

    int t = -3e4 - 100;

    while (uppest[u] != uppest[v])

    {

        if (dep[uppest[u]] < dep[uppest[v]])

            swap(u, v);

        t = max(t, query_max(bh[uppest[u]], bh[u], 1, n, 1));

        u = fa[uppest[u]];

    }

    if (dep[u] < dep[v])

        swap(u, v);

    t = max(t, query_max(bh[v], bh[u], 1, n, 1));

    return t;

}

int query_sum(int L, int R, int l, int r, int rt)

{

    if (L <= l && r <= R)

        return sum[rt];

    int m = (l + r) >> 1;

    int temp = 0;

    if (L <= m)

        temp += query_sum(L, R, lson);

    if (m < R)

        temp += query_sum(L, R, rson);

    return temp;

}

int get_sum(int u, int v)

{

    int t = 0;

    while (uppest[u] != uppest[v])

    {

        if (dep[uppest[u]] < dep[uppest[v]])

            swap(u, v);

        t += query_sum(bh[uppest[u]], bh[u], 1, n, 1);

        u = fa[uppest[u]];

    }

    if (dep[u] < dep[v])

        swap(u, v);

    t+=query_sum(bh[v], bh[u], 1, n, 1);

    return t;

}

void get_ans()

{

    rep1(i, 1, n)

        updata(bh[i], v[i],1, n, 1);

    int q;

    rei(q);

    char s[8];

    rep1(i, 1, q)

    {

        scanf("%s", s);

        if (s[0] == 'C')

        {

            int u, t;

            rei(u), rei(t);

            updata(bh[u], t, 1, n, 1);

        }

        else

        {

            int u, v;

            rei(u), rei(v);

            if (s[1] == 'M')

                printf("%d\n", get_max(u, v));

            else

                printf("%d\n", get_sum(u, v));

        }

    }

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    in();

    dfs1(1);

    dfs2(1, 1);

    get_ans();

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}