题解 P4116 【Qtree3】

· · 题解

update:我跟其他题解的做法不一样啊，其他题解都维护了 dfs 序，我的没有维护 dfs 序。

重链剖分，对于每一条重链，采用 set 维护这条重链上深度最小的点是什么。

对于 0 操作：若改成黑色，我们在这条重链的 set 中插入这个点；若改成白色，我们删除这个点。

对于 1 操作：不断地跳 top，更新答案。注意 v 所在重链的 set 中深度最小的黑点可能比 v 的深度大，而该重链深度最小的黑点深度都比 v 大，显然这条重链对答案没有贡献。

另外，由于查询的是 1 到 v，因此不必维护 dfs 序。

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<set>

using namespace std;

#define INF 1000000000
#define pprint(x) print(x),putchar(' ')
#define fprint(x) print(x),putchar('\n')

//#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
char BB[1 << 15],*SS = BB,*TT = BB;
inline long long read()
{
    long long x = 0;int f = 1;
    char ch = getchar();
    for(;!isdigit(ch);ch = getchar())
        if(ch == '-')
            f = -1;
    for(;isdigit(ch);ch = getchar())
        x = x * 10 + (ch ^ 48);
    return x * f;
}
void print(long long x)
{
    if(x < 0)
        putchar('-'),x = -x;
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

const int N = 100010;

int dep[N];
struct Tree_Partition
{
    struct edge
    {
        int nxt,to;
    }e[N << 1];
    int head[N],cnt;
    void add(int u,int v)
    {
        e[++cnt].to = v,e[cnt].nxt = head[u];
        head[u] = cnt;
    }
    void add_edge(int u,int v)
    {
        add(u,v),add(v,u);
    }
    int col[N],f[N],siz[N],son[N],top[N];
    struct cmp{bool operator()(const int &a,const int &b){ return dep[a] < dep[b]; }};
    set<int,cmp> s[N];
    void dfs1(int u,int fa)
    {
        f[u] = fa,dep[u] = dep[fa] + 1,siz[u] = 1;
        son[u] = 0;
        for(int i = head[u];i;i = e[i].nxt)
        {
            int v = e[i].to;
            if(v == fa)
                continue;
            dfs1(v,u);
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
    void dfs2(int u,int t)
    {
        top[u] = t;
        if(!son[u])
            return;
        dfs2(son[u],t);
        for(int i = head[u];i;i = e[i].nxt)
        {
            int v = e[i].to;
            if(v == f[u] || v == son[u])
                continue;
            dfs2(v,v);
        }
    }
    void change(int u)
    {
        if(col[u] ^= 1)
            s[top[u]].insert(u);
        else
            s[top[u]].erase(u);
    }
    int solve(int u)
    {
        int ans = -1;
        while(u)
        {
            int k = *s[top[u]].begin();
            if(s[top[u]].size())
                if(dep[k] <= dep[u])
                    ans = k;
            u = f[top[u]];
        }
        return ans;
    }
    void init()
    {
        dfs1(1,0);
        dfs2(1,1);
    }
}T;

int main()
{
    int n = read(),m = read();
    for(int i = 1;i < n;i++)
        T.add_edge(read(),read());
    T.init();
    while(m--)
    {
        int op = read();
        if(!op)
            T.change(read());
        else
            fprint(T.solve(read()));
    }
    return 0;
}