【Luogu】P2912牧场散步（TarjanLCA）

题目链接
老天……终于碰上一个除了模板之外的LCA题了
这道题用Tarjan来LCA。树上两个点的路径是唯一的，所以钦定一个根，两点间的路径就是两点到根的路径减去双倍的公共祖先到根的路径。
大概很好理解。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
using namespace std;

inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

struct Edge{
    int next,to,dis;
};
struct Pic{
    Edge edge[1000000];
    int head[1000000],num;
    bool vis[1000000];
    inline void add(int from,int to,int dis){
        edge[++num]=(Edge){head[from],to,dis};
        head[from]=num;
    }
}pic,que;
int dst[1000000];
int ans[2000][2000];
bool vis[1000000];
int father[1000000];
int find(int x){    return x==father[x]? x:father[x]=find(father[x]);    }
int unionn(int x,int y){    father[find(y)]=find(x);    }

void dfs(int x){
    vis[x]=1;
    for(int i=pic.head[x];i;i=pic.edge[i].next){
        if(vis[pic.edge[i].to])    continue;
        dst[pic.edge[i].to]=dst[x]+pic.edge[i].dis;
        dfs(pic.edge[i].to);
        unionn(x,pic.edge[i].to);
    }
    for(int i=que.head[x];i;i=que.edge[i].next)
        if(vis[que.edge[i].to])
            ans[x][que.edge[i].to]=ans[que.edge[i].to][x]=dst[x]+dst[que.edge[i].to]-(dst[find(que.edge[i].to)]<<1);
}

int a[1000000],b[1000000];

int main(){
    int n=read(),q=read();
    for(int i=1;i<n;++i){
        int from=read(),to=read(),dis=read();
        pic.add(from,to,dis);pic.add(to,from,dis);
        father[i]=i;
    }
    father[n]=n;
    for(int i=1;i<=q;++i){
        int from=read(),to=read();
        a[i]=from;b[i]=to;
        que.add(from,to,0);
        que.add(to,from,0);
    }
    dfs(1);
    for(int i=1;i<=q;++i)    printf("%d
",ans[a[i]][b[i]]);
    return 0;
}

【Luogu】P2912牧场散步（TarjanLCA）

相关推荐