树的直径相关-白红宇

树的直径相关

阅读量：4609 次

发布时间：2019-06-09

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

真的还有好多东西要学啊......

定理:

　　选取树 $T$ 的任意一个点 $i$ ,则与 $i$ 距离最远的节点 $r$ 必定是树中一条直径的端点.

定理:

　　经过树上一点i的最长路径的长度,一定等于:

　　情况1. $i$ 所引领的子树中,最大深度与次大深度之和.

　　情况2. $i$ 所引领的子树中的最大深度,加上 $i$ 到 $j$ 的最长路径,其中 $j$ 是一个不属于 $i$ 这个子树的节点.

　　当 $i$ 是树根时, $i$ 没有父节点,于是只会是情况1.

定理:

　　树 $T$ 的直径长度一定能表示为树 $T$ 上某个点 $i$ 所引领的子树中,最大深度与次大深度之和.

　　即, $\exists_{i\in V(T)}\; diameter = LargestDepth(subtree \ o \! f \ i) + SecondLargestDepth(subtree \ o \! f \ i)$

　　由于直径只有一个值,并且两个深度之和代表了一条路径的长度,

　　于是有$\forall_{i\in V(T)} \; diameter \ge LargestDepth(subtree \ o \! f \ i) + SecondLargestDepth(subtree \ o \! f \ i)$

定理:

　　点 $i$ 在某条直径上,当且仅当存在一条经过点 $i$ 的路径,它的长度(大于)等于直径.

AC VIJOS 1476 求在直径上的所有点. 直径可能有多条.

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 db eps=1e-80; 44 inline bool feq(db a,db b) 45 { return fabs(a-b)
                   
                     48 inline Type avg(const Type a,const Type b) 49 { return a+((b-a)/2); } 50 51 //=================================================================== 52 //=================================================================== 53 //=================================================================== 54 //=================================================================== 55 56 57 const int INF=(1<<30)-1; 58 59 struct edge 60 { 61 int in; 62 edge*nxt; 63 }pool[405000]; 64 edge*et=pool; 65 edge*eds[205000]; 66 void addedge(int i,int j) 67 { et->in=j; et->nxt=eds[i]; eds[i]=et++; } 68 #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt) 69 70 int n; 71 72 int dep[205000]; 73 int q[205000],qh,qt; 74 75 int deg[205000]; 76 77 int dia=0; 78 79 int mx[205000]; 80 int mxs[205000]; 81 int mxp[205000]; 82 int uv[205000]; 83 84 int f[205000]; 85 86 int main() 87 { 88 n=getint(); 89 for(int i=1;i
                    
                     in]==-1)106 {107 f[i->in]=x;108 dep[i->in]=dep[x]+1;109 q[qt++]=i->in;110 deg[x]++;111 }112 qh++;113 }114 115 memset(mxp,0xFF,sizeof(int)*(n+1));116 memset(mx,0xFF,sizeof(int)*(n+1));117 memset(mxs,0xFF,sizeof(int)*(n+1));118 qh=qt=0;119 for(int i=0;i
                     
                      in!=f[x])127 {128 if(mx[i->in]>mx[x])129 {130 mxs[x]=mx[x];131 mx[x]=mx[i->in];132 mxp[x]=i->in;133 }134 else if(mx[i->in]>mxs[x])135 {136 mxs[x]=mx[i->in];137 }138 }139 140 deg[f[x]]--;141 if(deg[f[x]]==0)142 { q[qt++]=f[x]; }143 144 mx[x]++;145 mxs[x]++;146 147 qh++;148 }149 150 qh=qt=0;151 uv[0]=0;152 FOREACH_EDGE(i,0)153 q[qt++]=i->in;154 155 while(qh!=qt)156 {157 int x=q[qh];158 159 uv[x]=max( uv[f[x]],160 x==mxp[f[x]] ? mxs[f[x]] : mx[f[x]]) +1;161 162 FOREACH_EDGE(i,x)163 if(i->in!=f[x]) q[qt++]=i->in;164 165 qh++;166 }167 168 for(int i=0;i