CF825G题解

题目大意

给定一颗有$n$个点的树，进行$q$次操作。

操作$1$：将第$x$个点染为黑色。

操作$2$：询问$x$到所有黑色点的路径上的编号最小的点。

操作强制在线。

题目思路

先给出做法，在给出证明。

以第一个黑点为根，做一次$dfs$，处理出$a_i$表示$i$到根的路径上编号最小的点。

询问操作的答案就是当前所有激活黑点的$a_i$与$a_x$取最小。

证明：

设答案点所在路径的两端为$u,v$。

无论当前路径是否经过根节点，$ans=\min (a_u,a_v)$。

因为两个点之间的路径可以拆分成$(u,lca(u,v))$，$(v,lca(u,v))$。

可以发现这两条路径都会被他们到根的路径包含，又因为每个黑点或询问的点与根的路径都会对答案做出贡献，所以就可以按上面的方法做。

具体实现参考代码。

#include
using namespace std;
int n,q,a[1000000+10],f[1000000+10],root=0,ans=INT_MAX,lastans=0;
vector<int> son[1000000+10];
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
void dfs(int u,int fa)
{   
    f[u]=min(u,f[fa]);
    for(auto v:son[u])
    {
        if(v==fa)
            continue;
        dfs(v,u);
    }
}
int main()
{
    n=read(),q=read();
    for(int i=1;i<=n-1;++i)
    {
        int u=read(),v=read();
        son[u].push_back(v);
        son[v].push_back(u);
    }
    for(int i=1;i<=n;++i)
        f[i]=INT_MAX;
    while(q--)
    {
        int opt=read(),u=read();
        u=(u+lastans)%n+1;
        if(opt==1)
        {
            a[u]=1;
            if(!root)
            {
                root=u;
                f[root]=root;
                dfs(root,root);
            }
            ans=min(ans,f[u]);
        }
        else
        {
            lastans=min(ans,f[u]);
            printf("%d\n",lastans);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62