【codevs 2370】小机房的树

原创
2016/10/30 09:57
阅读数 125

这个是题目吗
简单的lca,难度在于给数组命名
个人的想法是记录到根的距离,ans = dis[a] + dis[b] - dis[lca(a,b)] - dis[lca(a,b)]

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 50000 + 5;
const int LOG = 25;
int n,m;
struct edge
{
    int f,t,v;
}l[MAXN * 2];
int first[MAXN],next[MAXN * 2],tot;
void init()
{
    memset(first,0xfff,sizeof(first));
    tot = 0;
    return;
}
void build(int f,int t,int v)
{
    l[++tot] = (edge){f,t,v};
    next[tot] = first[f];
    first[f] = tot;
    return;
}
int anc[MAXN][LOG],deep[MAXN],rank[MAXN];
void make_tree(int x,int f,int v)
{
    anc[x][0] = f;
    deep[x] = deep[f] + 1;
    rank[x] = v;
    for(int i = first[x];i != -1;i = next[i])
        if(l[i].t != f)
            make_tree(l[i].t,x,v + l[i].v);
    return;
}
void make_lca()
{
    for(int j = 1;j <= log2(n);j ++)
        for(int i = 1;i <= n;i ++)
            anc[i][j] = anc[anc[i][j-1]][j-1];
    return;
}
int lca(int x,int y)
{
    if(deep[x] < deep[y])
        swap(x,y);
    for(int i = log2(n);i >= 0;i --)
        if(deep[anc[x][i]] >= deep[y])
            x = anc[x][i];
    if(x == y)
        return x;
    for(int i = log2(n);i >= 0;i --)
        if(anc[x][i] != anc[y][i])
            x = anc[x][i],y = anc[y][i];
    return anc[x][0];
}
int f,t,v;
int main()
{
    init();
    scanf("%d",&n);
    for(int i = 1;i < n;i ++)
    {
        scanf("%d %d %d",&f,&t,&v);
        build(f,t,v);
        build(t,f,v);
    }
    make_tree(0,0,0);
    make_lca();
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d",&f,&t);
        printf("%d\n",rank[f] + rank[t] - (rank[lca(f,t)] << 1));
    }
    return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部