[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 ;
}