BZOJ 1602 [Usaco2008 Oct]牧场行走

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1602

题意:给定一棵树和边权,若干询问,每次询问求两点间的距离。

思路:裸的LCA,树上两点间的距离为dis[u]+dis[v]-2*dis[lca(u,v)]

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=1000+5;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Edge{
    int u,v,w;
    Edge(int _,int __,int ___):u(_),v(__),w(___){}

    int To(int x){return x==u?v:u;}
};
int n,q;
int parent[maxn][16],dis[maxn],dep[maxn];
vector<Edge>edges;
vector<int>G[maxn];
void dfs(int u,int f){
    dep[u]=(f==-1?1:dep[f]+1);
    for (int i=0;i<(int)G[u].size();i++){
        Edge&e=edges[G[u][i]];
        int v=e.To(u);
        if (v==f) continue;
        dis[v]=dis[u]+e.w;
        parent[v][0]=u;
        dfs(v,u);
    }
}
void initLCA(){
    for (int k=0;k<15;k++){
        for (int v=1;v<=n;v++){
            if (parent[v][k]<0) continue;
            parent[v][k+1]=parent[parent[v][k]][k];
        }
    }
}
int lca(int u,int v){
    if (dep[u]>dep[v]) swap(u,v);
    for (int k=0;k<16;k++){
        if (((dep[v]-dep[u])>>k)&1) v=parent[v][k];
    }
    if (u==v) return u;
    for (int k=15;k>=0;k--){
        if (parent[u][k]!=parent[v][k]){
            u=parent[u][k];
            v=parent[v][k];
        }
    }
    return parent[u][0];
}
int main(){
    read(n),read(q);
    for (int i=1;i<=n-1;i++){
        int u,v,w;read(u),read(v),read(w);
        edges.push_back(Edge(u,v,w));
        int m=edges.size();
        G[u].push_back(m-1);
        G[v].push_back(m-1);
    }
    dis[1]=0;
    dfs(1,-1);
    initLCA();
    for (int i=1;i<=q;i++){
        int u,v;read(u),read(v);
        printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);
    }
    return 0;
}

发表评论

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