# 【codevs 2370】小机房的树

2016/10/30 09:57

#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