P5836 [USACO19DEC] Milk Visits S

· · 题解

P5836 [USACO19DEC] Milk Visits S

题目翻译：

给出一棵树，求任意两点间的唯一路径上是否有G或H

思路：

这是一道LCA的变形，这一次要维护的是路径上有的点。令f[u][i][0]为u节点的2^i次父亲节点。f[u][i][1]为其2^i次父亲节点的奶牛是否有G,同理f[u][i][2]为其2^i次父亲节点的奶牛是否有H。因此我们只需要维护这三个值，最后求lca时判断即可

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>e[N];
int f[N][32][3],dep[N];
int op[N];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0][0]=fa;
    f[u][0][1]=(op[u]==1)||(op[fa]==1);
    f[u][0][2]=(op[u]==2)||(op[fa]==2);
    for(int i=1;i<=30;i++){
        f[u][i][0]=f[f[u][i-1][0]][i-1][0]; 
        f[u][i][1]=(f[u][i-1][1])||(f[f[u][i-1][0]][i-1][1]);
        f[u][i][2]=(f[u][i-1][2])||(f[f[u][i-1][0]][i-1][2]);
    }
    for(auto ed:e[u]){
        if(ed==fa)continue;
        dfs(ed,u);
    }
}
int lca(int x,int y,int opt){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=30;i>=0;i--){
        if(dep[f[x][i][0]]<dep[y])continue;
        if(f[x][i][opt])return 1;
        x=f[x][i][0];
    }
    if(x==y){
        if(op[x]==opt)return 1;
        else return 0;
    }
    for(int i=30;i>=0;i--){
        if(f[x][i][0]==f[y][i][0])continue;
        if(f[x][i][opt] || f[y][i][opt])return 1;
        x=f[x][i][0];
        y=f[y][i][0];
    }
    if(f[x][0][opt] || f[y][0][opt])return 1;
    return 0;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        char opt;
        cin>>opt;
        op[i]=(opt=='G'?1:2);
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    while(m--){
        int u,v;
        char opt;
        cin>>u>>v>>opt;
        cout<<lca(u,v,(opt=='G'?1:2));
    }
}

最近公共祖先讲解