PWALK - Dạo chơi đồng cỏ
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
#define maxn 1010
using namespace std;
int n,a[maxn][maxn],e[maxn][11],d[maxn],f[maxn],h[maxn];
void visit(int x,int y)
{
d[x]=y;
int i;
fr(i,1,n)
if (i!=y && a[x][i])
{
f[i]=f[x]+a[x][i];
h[i]=h[x]+1;
visit(i,x);
}
}
int lca(int x,int y)
{
int i;
if (h[x]<h[y]) swap(x,y);
frr(i,10,0)
if (h[x]-(1<<i)>=h[y])
x=e[x][i];
if (x==y) return x;
frr(i,10,0)
if (e[x][i]!=-1 && e[x][i]!=e[y][i])
x=e[x][i], y=e[y][i];
return d[x];
}
int main()
{
int q,i,j,x,y,z;
cin >> n >> q;
fr(i,1,n-1)
{
cin >> x >> y >> z;
a[x][y]=z; a[y][x]=z;
}
fr(i,1,n)
fr(j,0,10)
e[i][j]=-1;
visit(1,0);
d[1]=-1;
fr(i,2,n) e[i][0]=d[i];
fr(j,1,10)
fr(i,1,n)
if (e[i][j-1]!=-1)
e[i][j]=e[e[i][j-1]][j-1];
while (q--)
{
cin >> x >> y;
z=lca(x,y);
cout << f[x]+f[y]-2*f[z] << endl;
}
return 0;
}