博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 1655
阅读量:6342 次
发布时间:2019-06-22

本文共 1537 字,大约阅读时间需要 5 分钟。

#include
#include
#include
#include
#include
#define MAXN 20010using namespace std;typedef struct{ int to,next;}Node;typedef struct PP{ int id,par; bool operator < (const PP &a) const { if(par == a.par) return id < a.id; return par < a.par; }}Partition;Node edge[MAXN*2];Partition P[MAXN];int head[MAXN],vis[MAXN],cnt[MAXN],N;void addedge(int u,int v,int k){ edge[k].to = v; edge[k].next = head[u]; head[u] = k;}int dfs(int s){ vis[s] = cnt[s] = 1; for(int i = head[s];~i;i = edge[i].next){ int u = edge[i].to; if(!vis[u]) cnt[s] += dfs(u); } return cnt[s]--;}void dfs_partition(int s){ vis[s] = 1; P[s].id =s; P[s].par = N - cnt[s] - 1; for(int i = head[s];~i;i = edge[i].next){ int u = edge[i].to; if(!vis[u]){ P[s].par = max(P[s].par,cnt[u]+1); dfs_partition(u); } }}int main(){ int t,u,v;// freopen("in.c","r",stdin); scanf("%d",&t); while(t--){ memset(head,-1,sizeof(head)); scanf("%d",&N); int k = 1; for(int i = 1;i <= N-1;i ++){ scanf("%d%d",&u,&v); addedge(u,v,k++); addedge(v,u,k++); } memset(vis,0,sizeof(vis)); dfs(1); memset(vis,0,sizeof(vis)); dfs_partition(1); sort(P+1,P+N+1); printf("%d %d\n",P[1].id,P[1].par); } return 0;}

转载于:https://www.cnblogs.com/wangzhili/p/3950268.html

你可能感兴趣的文章
运维学习之路
查看>>
Azure迁移托管磁盘虚拟机到新账号下
查看>>
我的友情链接
查看>>
HTML空格占位符
查看>>
CentOS 5.3通过yum升级php到最新版本的方法
查看>>
Heartbeat的编译安装配置
查看>>
centos6和centos7手动扩展PHP的IMAP模块
查看>>
Cisco路由器的配置寄存器
查看>>
CentOS 5.6 安装 Oracle 11g R2
查看>>
Java中的位运算符
查看>>
思科交换机重置enable密码步骤
查看>>
完美解决 WIN2003 SERVER 终端服务120天限制!
查看>>
快速深入一门语言的绝招
查看>>
jQuery学习二 创建对象
查看>>
Mysql导入导出sql脚本
查看>>
Java NIO 系列教程
查看>>
Java IO流学习总结
查看>>
Linux双网卡配置
查看>>
ORACLE sqlplus基本操作
查看>>
spring 为某类注入的属性 其子类无法使用
查看>>