记录编号	438378	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.216 s
提交时间	2017-08-15 21:47:45	内存使用	2.85 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

bool read_cmd(void) { 
    register char tmp = getc();
    while(!isgraph(tmp)) tmp = getc();
    if(tmp == 'Q') return true;
    return false;
}

#define MAXN (100010)
#define INF (0x7fffffff)
typedef long long LL;

struct NODE{ 
    int mx, mi;
    NODE *ls, *rs;

    NODE() { 
        ls = rs = NULL;
    }
};

struct EDGE{ 
    int to;
    EDGE *ne;
    EDGE(int t, EDGE *n) { 
        to = t, ne = n;
    }
};

struct DATA{ 
    int a, b;
    DATA() { ;}
    DATA(int a, int b) { 
        this->a = a, this->b = b;
    }
};

void dfs(int u);
inline void add_edge(int fr, int to);
NODE *Build(int l, int r);
void Update(NODE *node, int k, int w, int L, int R);
DATA Query(NODE *node, int l, int r, int L, int R);

vector<DATA> roads;
EDGE *head[MAXN];
NODE *root;
int dfn[MAXN], id[MAXN], siz[MAXN];
int val[MAXN], fa[MAXN];
int N, Q, arg, *temp;

int main() { 
#ifndef LOCAL
    freopen("westward.in", "r", stdin);
    freopen("westward.out", "w", stdout);
#endif
    N = read(), Q = read();
    temp = val;
    for(int i = 0; i < N; ++i) *(++temp) = read();
    for(int i = 1, fr, to; i < N; ++i) { 
        fr = read(), to = read();
        add_edge(fr, to);
        roads.push_back(DATA(fr, to));
    }
    dfs(1);
    root = Build(1, N);
    DATA part1, part2;
    for(int i = 0, a, b; i < Q; ++i) { 
        if(read_cmd()) { 
            arg = read() - 1;
            a = roads[arg].a;
            b = roads[arg].b;
            if(fa[b] == a) a ^= b ^= a ^= b;
            part1 = Query(root, 1, dfn[a] - 1, 1, N);
            part2 = Query(root, dfn[a] + siz[a], N, 1, N);
            part2 = DATA(max(part1.a, part2.a), min(part1.b, part2.b));
            part1 = Query(root, dfn[a], dfn[a] + siz[a] - 1, 1, N);
            printf("%lld\n", (LL)part1.a * (LL)part1.b + (LL)part2.a * (LL)part2.b);
        } else Update(root, read(), dfn[read()], 1, N);
    }
}

void dfs(int u) { 
    static int cnt = 0;
    siz[u] = 1;
    id[dfn[u] = ++cnt] = u;
    for(register EDGE *e = head[u]; e; e = e->ne) 
        if(!dfn[e->to]) fa[e->to] = u, dfs(e->to), siz[u] += siz[e->to];
    return ;
}

inline void add_edge(int fr, int to) { 
    head[fr] = new EDGE(to, head[fr]);
    head[to] = new EDGE(fr, head[to]);
    return ;
}

NODE *Build(int l, int r) { 
    NODE *p = new NODE();
    if(l ^ r) { 
        int mid = (l + r) >> 1;
        p->ls = Build(l, mid);
        p->rs = Build(mid + 1, r);
        p->mx = max(p->ls->mx, p->rs->mx);
        p->mi = min(p->ls->mi, p->rs->mi);
    } else p->mx = p->mi = val[id[l]];
    return p;
}

void Update(NODE *node, int k, int w, int L, int R) { 
    if(L == R) node->mx = node->mi = k;
    else { 
        int mid = (L + R) >> 1;
        if(w <= mid) Update(node->ls, k, w, L, mid);
        else Update(node->rs, k, w, mid + 1, R);
        node->mx = max(node->ls->mx, node->rs->mx);
        node->mi = min(node->ls->mi, node->rs->mi);
    }
    return ;
}

DATA Query(NODE *node, int l, int r, int L, int R) { 
    if(l > r) return DATA(-INF, INF);
    if(l == L && r == R) return DATA(node->mx, node->mi);
    int mid = (L + R) >> 1;
    if(r <= mid) return Query(node->ls, l, r, L, mid);
    if(mid < l) return Query(node->rs, l, r, mid + 1, R);
    register DATA a = Query(node->ls, l, mid, L, mid);
    register DATA b = Query(node->rs, mid + 1, r, mid + 1, R);
    return DATA(max(a.a, b.a), min(a.b, b.b));
}