CSAcademy Round #63 (Div. 2 only) Root LCA Queries

题目链接https://csacademy.com/contest/round-63/task/root-lca-queries/

题意:给你一棵无根树,若干询问,每次询问a,b,c,问有多少个点为根节点的时候ab的最近公共祖先是c

思路:其实不难想到只有当cab的路径上的时候才有可能成为他们的最近公共祖先,而答案也很明显就是以c为根的时候不包含ab的所有子树的节点数之和。如果我们在确定c有可能成为他们公共祖先的情况下能够知道是c的哪个子节点包含了ab即可计数,那么我们来尝试解决第一个问题。我们先随便找个点为根dfs一下求出DFS序以及每个节点为根节点的子树的节点数sz[x]。这里有两种情况,如果ac的子树里我们直接倍增法找到最靠近ca的祖先节点即可,不然祖先节点就是c的父亲节点,而判断a是否在c的子树里,我们用之前求好的DFS序即可O(1)判断,因为DFS序本来就是把子树节点连续的映射在一段区间上,至此第一个问题就可以解决了。如果ab找到的祖先节点都是一样的说明cab的路径外,此时不满足条件,否则直接计数就可以了,时间复杂度O((N+Q)log N)

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,q,dfs_clock,L[maxn],R[maxn],dep[maxn],parent[maxn][18],sz[maxn];
vector<int>G[maxn];
void dfs(int u,int f){
    sz[u]=1;
    dep[u]=dep[f]+1;
    L[u]=++dfs_clock;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        parent[v][0]=u;
        sz[u]+=sz[v];
    }
    R[u]=dfs_clock;
}
void init(){
    for (int j=1;j<=17;j++){
        for (int i=1;i<=n;i++){
            if (parent[i][j-1]<0) continue;
            parent[i][j]=parent[parent[i][j-1]][j-1];
        }
    }
}
bool isin(int v,int u){
    return (L[u]<=L[v] && R[v]<=R[u]);
}
int move(int from,int to){
    if (isin(from,to)){
        for (int k=0;k<=17;k++){
            if (((dep[from]-dep[to]-1)>>k)&1) from=parent[from][k];
        }
        return from;
    }
    else return parent[to][0];
}
int main(){
    cin>>n>>q;
    memset(parent,-1,sizeof(parent));
    for (int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    init();
    for (;q--;){
        int a,b,c;cin>>a>>b>>c;
        int ta=move(a,c),tb=move(b,c);
        if (ta==tb) puts("0");
        else{
            if (dep[ta]>dep[tb]) swap(ta,tb);
            if (dep[ta]<dep[c] && dep[c]<dep[tb]) cout<<n-(n-sz[c]+sz[tb])<<endl;
            if (dep[ta]>dep[c] && dep[c]<dep[tb]) cout<<n-sz[ta]-sz[tb]<<endl;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注