POJ3417 闇の连锁

书P380

① LCA:https://blog.nowcoder.net/n/cbc02f19ffa7450d9298b9474c6bd4b8

② dfs:https://blog.nowcoder.net/n/abf5e27bb5c243ebb12d8aced6e11411

时间复杂度 O(n+m)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int MAXN = 1e5 + 5;  // 最大节点数
const int LOG_N = 40; //只能是40，不然会TLE 
int n, m;
int head[MAXN];
struct Edge
{
    int to, next;
}edge[MAXN * 2];
int depth[MAXN]; // 节点深度
int parent[LOG_N][MAXN];  // parent[k][i]表示 i 向上走 2^k 步能到达的节点
int hide[MAXN]; // u到它的父亲节点所连边被覆盖过几次
int cnt;
void add(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void dfs(int pre, int u, int d)
{
    parent[0][u] = pre;
    depth[u] = d;
    for(int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v != pre) dfs(u, v, d + 1);
    }
}
void init()
{
    int root = 1;
    dfs(-1, root, 0);//pre代表父节点，u是当前点，d是深度 
    for(int k = 1; k < LOG_N; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(parent[k - 1][i] < 0) parent[k][i] = -1;
            else parent[k][i] = parent[k - 1][parent[k - 1][i]];//树上倍增的经典 
        }
    }
}
int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
    for(int i = 0; i < LOG_N; i++) // u 和 v 向上走到同一深度
    {
        if((depth[v] - depth[u]) >> i & 1) // 把 (depth[v] - depth[i]) 化成二进制后可以看到，就是找到所有 1 的位置
        {
            v = parent[i][v];
        }
    }
    if(v == u) return u;
    for(int i = LOG_N - 1; i >= 0; i--) // 找 lca
    {
        if(parent[i][u] != parent[i][v]) // 如果相同，那么一定是公共祖先或公共祖先之上的节点
        {
            u = parent[i][u];
            v = parent[i][v];
        }
    }
    return parent[0][u];
}
void dfs2(int pre, int u)
{
    for(int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v != pre)
        {
            dfs2(u, v);
            hide[u] += hide[v];//求以u为根，子树的节点权值总和 
        }
    }
}
int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        memset(head, -1, sizeof head);
        for(int i = 1; i < n; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            add(x, y);
            add(y, x);
        }
        init();
        for(int i = 0; i < m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            int node = lca(x, y);
            hide[x]++;
            hide[y]++;
            hide[node] -= 2;
        }
        dfs2(-1, 1);
        int ans = 0;
        for(int i = 2; i <= n; i++) 
        {
            if(hide[i] == 0) ans += m;//没有边覆盖，可以随机一条非树边 
            else if(hide[i] == 1) ans++;//只有一条非树边覆盖，答案唯一 
        }
        printf("%d\n", ans);
        break;//原文没有加进来 
    }
    return 0;
}

来源：https://blog.csdn.net/weixin_33946605/article/details/93663457