题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2545
思路:dist[u]表示节点u到根节点的距离,然后在查找的时候更新即可,最后判断dist[u],dist[v]的大小即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 101000 int n,m;
int parent[MAXN];
int dist[MAXN]; int Find(int x)
{
if(x==parent[x]){
return parent[x];
}
int tmp=parent[x];
parent[x]=Find(parent[x]);
dist[x]+=dist[tmp];//更新到根节点的距离
return parent[x];
} int main()
{
int u,v;
while(~scanf("%d%d",&n,&m)){
if(n==&&m==)break;
for(int i=;i<=n;i++){
parent[i]=i;
dist[i]=;
}
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
parent[v]=u;
dist[v]=;
}
while(m--){
scanf("%d%d",&u,&v);
Find(u);
Find(v);
if(dist[u]<=dist[v]){
puts("lxh");
}else
puts("pfz");
}
}
return ;
}