[HEOI2016/TJOI2016]树

思路

做的时候也是糊里糊涂的
就是求最大值的线段树

错误

线段树写错了

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=6e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
struct edge {
    int v,nxt;
}e[N<<1];
int head[N],tot;
void add_edge(int u,int v) {
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int n,m;
int a[N],idx[N],top[N],son[N],siz[N],f[N],dep[N],cnt;
void dfs1(int u,int fa) {
    f[u]=fa;
    siz[u]=1;
    dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(fa==v) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
}
void dfs2(int u,int topf) {
    idx[u]=++cnt;
    a[cnt]=u;
    top[u]=topf;
    if(!son[u]) return;
    dfs2(son[u],topf);
    for(int i=head[u];i;i=e[i].nxt)
        if(!idx[e[i].v]) dfs2(e[i].v,e[i].v);
}
namespace seg_tree {
    #define ls rt<<1
    #define rs rt<<1|1
    struct node {
        int l,r,ma;
    }e[N<<2];
    void pushup(int rt) {
        e[rt].ma=max(e[ls].ma,e[rs].ma);
    }
    void build(int l,int r,int rt) {
        e[rt].l=l,e[rt].r=r;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,ls);
        build(mid+1,r,rs);
    }
    void modify(int L,int rt) {
        if(e[rt].l==e[rt].r) {e[rt].ma=L;return;}
        int mid=(e[rt].l+e[rt].r)>>1;
        if(L<=mid) modify(L,ls);
        else modify(L,rs);
        pushup(rt);
    }
    int query(int L,int R,int rt) {
        if(L<=e[rt].l&&e[rt].r<=R) return e[rt].ma;
        int mid=(e[rt].l+e[rt].r)>>1,ans=0;
        if(L<=mid) ans=max(ans,query(L,R,ls));
        if(R>mid) ans=max(ans,query(L,R,rs));
        return ans;
    }
}
int QQ(int x,int y) {
    int ans=0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=max(seg_tree::query(idx[top[x]],idx[x],1),ans);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=max(ans,seg_tree::query(idx[x],idx[y],1));
    return a[ans];
}
int main() {
    n=read(),m=read();
    FOR(i,2,n) {
        int x=read(),y=read();
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    seg_tree::build(1,n,1);
    seg_tree::modify(idx[1],1);
    FOR(i,1,m) {
        char s[10];
        scanf("%s",s);
        int x=read();
        if(s[0]=='C') seg_tree::modify(idx[x],1);
        if(s[0]=='Q') printf("%d\n",QQ(x,1));
    }
    return 0;
}