poj 1655 树的重心 && define注意事项-白红宇

poj 1655 树的重心 && define注意事项

阅读量：4945 次

发布时间：2019-06-11

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

http://blog.csdn.net/acdreamers/article/details/16905653

题意:给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的.

分析:首先要知道什么是树的重心,树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重

心后，生成的多棵树尽可能平衡. 实际上树的重心在树的点分治中有重要的作用, 可以避免N^2的极端复杂度（从退化链的一端出发），保证

NlogN的复杂度, 利用树型dp可以很好地求树的重心.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    using namespace std;#define mem(a,b) memset(a,b,sizeof(a))#define pf printf#define sf scanf#define spf sprintf#define pb push_back#define debug printf("!\n")#define MAXN 20000+5#define MAX(a,b) a>b?a:b#define blank pf("\n")#define LL long long#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define pqueue priority_queue#define INF 0x3f3f3f3f#define ls (rt<<1)#define rs (rt<<1|1)int n,m;int ptr = 1,head[MAXN],vis[MAXN];int res,ans,son[MAXN];struct node{ int y,val,next;}tree[MAXN<<1];void add(int fa,int son){ tree[ptr].y = son; tree[ptr].next = head[fa]; head[fa] = ptr++;}void dfs(int root){ vis[root] = 1; son[root] = 0; int tmp = 0; for(int i=head[root];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y); son[root] += son[y]+1; tmp = max(son[y]+1,tmp); } tmp = max(tmp,n-son[root]-1); if(tmp

在这题里出现了这样一个情况，导致我第一次时TLE了

#define MAXN 20000+5struct node{    int y,val,next;}tree[MAXN*2];

因为是无向边，我习惯性地乘了2，导致结果错误。这里其实算出来的是20000+5*2 = 20010

改正有这样两种方法：

1.移位运算级低，可以直接用

#define MAXN 20000+5struct node{    int y,val,next;}tree[MAXN<<1];

2.define加括号

#define MAXN (20000+5)struct node{    int y,val,next;}tree[MAXN*2];

转载于:https://www.cnblogs.com/qlky/p/5780933.html

你可能感兴趣的文章