题解 P4092 【[HEOI2016/TJOI2016]树】

· · 题解

P4092 [HEOI2016/TJOI2016]树

（题解居然没有和我方法一样的）

这题不用建树

fa[i]表示i的父节点

据说这样暴力就可以了

但是！

有优化的方法！

时间戳

nearfa[i] 表示 点i 最近的一个打了标记的祖先，默认1

t[i] 表示 这个点最后一次被查询是在第几次标记之后，默认1

cnt 表示 执行了几次标记操作 ，为了方便，cnt从1开始

执行标记操作时，如果这个点已经被标记了，就不用再标记了。

否则标记，cnt++;

find(u) 函数：（递归实现）

如果点u被标记，返回u （废话）；

如果t[u]==cnt （在最后一次标记后已经访问过），直接返回nearfa[u] ；

否则, 将 t[u] 设为cnt，同时将 nearfa[u] 设为 find(fa[u]) , 返回 ; (递归实现)

上代码：

#include<cstdio>

int fa[100050];
bool flag[100050];
int t[100050],nearfa[100050],cnt=1;

int find(int u)
{
    if(flag[u])return u;//如果点u被标记，返回u
    if(t[u]==cnt)return nearfa[u];//在最后一次标记后已经访问过
    t[u]=cnt;//表示在此次标记后已被访问
    return nearfa[u]=find(fa[u]);//继续递归
}

int main(void)
{
    flag[1]=1; fa[1]=1;
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        fa[v]=u;
    }
    for(int i=1;i<=n;i++)t[i]=nearfa[i]=1;//初始化
    for(int i=0;i<q;i++)
    {
        char oper;
        int u;
        scanf("\n%c %d",&oper,&u);
        if(oper=='C')
            {if(!flag[u])flag[u]=1,cnt++;}//如果没被标记，标记
        else printf("%d\n",find(u));
    }
    return 0;
}

时间复杂度：(最坏) O(n^2)

数据强一点可以卡掉