[HDU 5927] Auxiliary Set （DFS+树上LCA）

链接

HDU 5927

题意

CCPC东北四省的1006。

给出一个树，和一个点集，点集外的点为“重要的点”，如果某个点集内的点是两个“重要的点的LCA”，那么它也是“重要的点”，其他点为“非重要的点”。

求出重要的点的个数。

数据规模看原题吧，不能直接dfs，会超时。

题解

这是一个LCA的题目（第一次做正经的LCA题），用到一个LCA的重要性质，同一个节点的不同子树中的任何节点的LCA为该节点本身。

先假定集合内的点都是“非重要”的，对非重要的点向下dfs，找到每个子树中是否含有“重要的点”，如果有2个以上这样的子树，那么该节点也是“重要的点”。

需要注意如果某节点含有重要的点，那么该节点也是“携带者”，需要用一个标记记录。

这题有个坑点是需要对集合内的点单独建树，如果在原树上dfs会T掉的，因为这样会遍历到集合外的点（我感觉不该卡这个的。。。）。

另外，LCA相关的题目好像都要先跑一遍dfs得出父节点。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define maxn (100010)
vector<int> son[maxn], use[maxn], b;
int fa[maxn], cnt[maxn], unim[maxn], vis[maxn];
void findfa(int u, int f)
{
    fa[u] = f;
    for(int i = , v; i < son[u].size(); i++)
    if((v = son[u][i]) != f) {
        findfa(v, u);
        cnt[u]++;
    }
}
int delta;
int dfs(int u)
{
    int unum = ;
    for(int i = , v; i < use[u].size(); i++)
    if((v = use[u][i]) != fa[u]) {
        if(unim[v] && !vis[v]) dfs(v);
        if(unim[v]) unum++;
    }
    if(cnt[u] - unum > ) unim[u] = ;
    if(cnt[u] - unum > ) delta++;
    vis[u] = ;
}
int main()
{
    int T, kase = ;
    cin >> T;
    while(T--)
    {
        int n, q;
        cin >> n >> q;
        for(int i = , u, v; i < n-; i++)
        {
            scanf("%d%d", &u, &v);
            son[u].push_back(v);
            son[v].push_back(u);
        }
        findfa(, );
        printf("Case #%d:\n", ++kase);
        while(q--)
        {
            int m;
            cin >> m;
            for(int i = , u; i < m; i++)
            {
                scanf("%d", &u);
                b.push_back(u);
                unim[u] = ;
            }
            for(int i = , u, f; i < m; i++)
            {
                u = b[i];
                f = fa[u];
                if(unim[f]) use[f].push_back(u);
            }
            for(int i = , u; i < m; i++)
            if(!vis[u = b[i]]) {
                dfs(u);
            }
            printf("%d\n", n - m + delta);

            for(int i = , u; i < m; i++)
            {
                u = b[i];
                use[u].clear();
                unim[u] = ;
                vis[u] = ;
            }
            delta = ;
            b.clear();
        }
        for(int i = ; i <= n; i++)
        {
            son[i].clear();
            cnt[i] = ;
        }

    }
    return ;
}