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;
}

Download