注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2545  

2013-03-10 11:27:09|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=2545
题意:给一棵树,如果树上的某个节点被某个人占据,则它的所有儿子都被占据,lxh和pfz初始时分别站在两个节点上,谁当前所在的点被另一个人占据,他就输了比赛,问谁能获胜
题解:可以用并查集+路径优化(一定要路径优化,否则会超时)先求出两个点离根结点的距离,然后再比较

/*
* test.cpp
*
* Created on: 2013-03-10
* Author: fudq
* 因为数据量比较大,应利用并查集+路径压缩的方法,先算出改点离根结点的距离,然后再比较
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 100010
int father[N],dis[N];

int find(int a)
{
if(a==father[a])
{
dis[a]=0;
return a;
}
int t=father[a];
father[a]=find(t);
dis[a]+=dis[t];
return father[a];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int n,m,i,a,b,t;
while(scanf("%d%d",&n,&m)!=EOF && (n||m))
{
for(i=0;i<=n;i++)
{
father[i]=i;
dis[i]=1;
}
for(i=0;i<n-1;i++)
{
scanf("%d%d",&a,&b);
father[b]=a;
}
while(m--)
{
scanf("%d%d",&a,&b);
t=find(a);t=find(b);
if(dis[a]<=dis[b])
printf("lxh\n");
else
printf("pfz\n");
}
}
return 0;
}



  评论这张
 
阅读(88)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018