[POJ 3237] 树的维护 - sxysxy - 319111

记录编号	319111	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.957 s
提交时间	2016-10-10 13:35:15	内存使用	1.27 MiB
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <list>
#include <queue>
#include <vector>
using namespace std;
int fast_read()
{
    int r;
    char c;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return r;
}
#define MAXN 10002
struct edge
{
    int from, to;
    int value;
    void read()
    {
        from = fast_read();
        to = fast_read();
        value = fast_read();
    }
}edges[MAXN];
vector<int> G[MAXN];
int deep[MAXN];
int top[MAXN], parent[MAXN], size[MAXN], son[MAXN];
int has[MAXN];
int hasid = 0;
void dfs(int u, int f, int d)
{
    size[u] = 1;
    parent[u] = f;
    deep[u] = d;
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != f)
        {
            dfs(to, u, d+1);
            size[u] += size[to];
            if(size[son[u]] < size[to])
                son[u] = to;
        }
    }
}
void dfs(int u, int tp)
{
    top[u] = tp;
    has[u] = ++hasid;
    if(!son[u])return;
    dfs(son[u], tp);
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != parent[u] && to != son[u])
            dfs(to, to);
    }
}
int val[MAXN];
struct node
{
    int l, r;
    int ls, rs;
    bool lazy;
    int maxv, minv;
    void flip()
    {
        /*
        int t = minv;
        minv = -maxv;
        maxv = -t;
        */
        swap(maxv, minv);
        maxv = -maxv;
        minv = -minv;
    }
}ns[MAXN<<1];
int root = 1;
int last = root;
inline void up(node &d)
{
    d.maxv = max(ns[d.ls].maxv, ns[d.rs].maxv);
    d.minv = min(ns[d.ls].minv, ns[d.rs].minv);
}
int build(int l, int r)
{
    if(l > r)return 0;
    int cur = last++;
    node &d = ns[cur];
    d.l = l;
    d.r = r;
    d.lazy = false;
    if(l == r)
    {
        d.minv = val[l];
        d.maxv = val[l];
    }else
    {
        int m = (l+r)>>1;
        d.ls = build(l, m);
        d.rs = build(m+1, r);
        up(d);
    }
    return cur;
}
void down(node &d)
{
     if(d.lazy)
     {
         ns[d.ls].lazy = !ns[d.ls].lazy;
         ns[d.rs].lazy = !ns[d.rs].lazy;
         ns[d.ls].flip();
         ns[d.rs].flip();
         d.lazy = false;
     }
}
void update(int c, int p, int v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == p && d.l == d.r)
    {
        d.maxv = v;
        d.minv = v;
    }else
    {
        down(d);
        if(d.ls && p <= ns[d.ls].r)update(d.ls, p, v);
        else if(d.rs && p >= ns[d.rs].l)update(d.rs, p, v);
        up(d);
    }
}
void turn(int c, int l, int r)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == l && d.r == r)
    {
        d.lazy = !d.lazy;
        d.flip();
    }else
    {
        down(d);
        if(l >= ns[d.rs].l)turn(d.rs, l, r);
        else if(r <= ns[d.ls].r)turn(d.ls, l, r);
        else 
        {
            turn(d.ls, l, ns[d.ls].r);
            turn(d.rs, ns[d.rs].l, r);
        }
        up(d);
    }
}
inline void change(int p, int v)
{
    update(1, has[edges[p].from], v);
}
int querytree(int c, int l, int r)
{
    if(!c)return -0x7ffffffe;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        return d.maxv;
    else
    {
        down(d);
        if(l >= ns[d.rs].l)return querytree(d.rs, l, r);
        else if(r <= ns[d.ls].r)return querytree(d.ls, l, r);
        else 
            return max(querytree(d.ls, l, ns[d.ls].r), querytree(d.rs, ns[d.rs].l, r));
    }
}
void negate_uv(int u, int v)
{
    int t1 = top[u], t2 = top[v];
    while(t1 != t2)
    {
        if(deep[t1] < deep[t2])
        {
            swap(t1, t2);
            swap(u, v);
        }
        turn(1, has[t1], has[u]);
        u = parent[t1];
        t1 = top[u];
    }
    if(u == v)return;
    else
    {
        if(deep[u] > deep[v])swap(u, v);
        turn(1, has[son[u]], has[v]);
    }
}
int querymax(int u, int v)
{
    int ans = -0x7ffffffe;
    int t1 = top[u], t2 = top[v];
    while(t1 != t2)
    {
        if(deep[t1] < deep[t2])
        {
            swap(t1, t2);
            swap(u, v);
        }
        ans = max(ans, querytree(1, has[t1], has[u]));
        u = parent[t1];
        t1 = top[u];
    }
    if(u == v)return ans;
    else
    {
        if(deep[u] > deep[v])swap(u, v);
        return max(ans, querytree(1, has[son[u]], has[v]));
    }
}
void clear(int t)
{
    while(t--)getchar();
}
int main()
{
    freopen("maintaintree.in", "r", stdin);
    freopen("maintaintree.out", "w", stdout);
    int n;
    n = fast_read();
    for(int i = 1; i < n; i++)
    {
        edge &e = edges[i];
        e.read();
        G[e.from].push_back(e.to);
        G[e.to].push_back(e.from);
    }
    dfs(1, 0, 1);
    dfs(1, 1);
    for(int i = 1; i < n; i++)
    {
        edge &e = edges[i];
        if(deep[e.from] < deep[e.to])swap(e.from, e.to);
        val[has[e.from]] = e.value;
    }
    ns[0].maxv = -0x7ffffffe;
    ns[0].minv = 0x7fffffff;
    build(1, hasid);
    bool flag = true;
    while(flag)
    {
        char c;
        int a1, a2;
        while(!isalpha(c = getchar()));
        switch(c)
        {
            case 'Q':
                clear(4);
                a1 = fast_read();
                a2 = fast_read();
                printf("%d\n", querymax(a1, a2));
            break;
            case 'C':
                clear(5);
                a1 = fast_read();
                a2 = fast_read();
                change(a1, a2);
            break;
            case 'N':
                clear(5);
                a1 = fast_read();
                a2 = fast_read();
                negate_uv(a1, a2);    //标准库里有个结构体叫negate...
            break;
            case 'D':
                clear(3);
                flag = false;
            break;
        }
    }
    return 0;
}