codevs 1814 最长链题解
codevs 1814 最长链题解
题目描述 <small>Description</small>
现给出一棵N个结点二叉树，问这棵二叉树中最长链的长度为多少，保证了1号结点为二叉树的根。
输入描述 <small>Input Description</small>
输入的第1行为包含了一个正整数N，为这棵二叉树的结点数，结点标号由1至N。
接下来N行，这N行中的第i行包含两个正整数l[i], r[i]，表示了结点i的左儿子与右儿子编号。如果l[i]为0，表示结点i没有左儿子，同样地，如果r[i]为0则表示没有右儿子。
输出描述 <small>Output Description</small>
输出包括1个正整数，为这棵二叉树的最长链长度。
样例输入 <small>Sample Input</small>
5
2 3
4 5
0 6
0 0
0 0
样例输出 <small>Sample Output</small>
4
数据范围及提示 <small>Data Size & Hint</small>
【样例说明】
4-2-1-3-6为这棵二叉树中的一条最长链。
【数据规模】
对于10%的数据，有N≤10；
对于40%的数据，有N≤100；
对于50%的数据，有N≤1000；
对于60%的数据，有N≤10000；
对于100%的数据，有N≤100000，且保证了树的深度不超过32768。
【提示】
关于二叉树：
二叉树的递归定义：二叉树要么为空，要么由根结点，左子树，右子树组成。左子树和右子树分别是一棵二叉树。
请注意，有根树和二叉树的三个主要差别：
1. 树的结点个数至少为1，而二叉树的结点个数可以为0；
2. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
3. 树的结点无左、右之分，而二叉树的结点有左、右之分。
关于最长链：
最长链为这棵二叉树中一条最长的简单路径，即不经过重复结点的一条路径。可以容易证明，二叉树中最长链的起始、结束结点均为叶子结点。
解析：
寻求最长链的模板题.
输入时要注意将其父节点和子节点进行前向星连边,边权都设为1.
随机找一个点,其实也就是根节点1,然后就跑一遍DFS,寻求最大值,并且记录下该最大值的标号.然后再从此标号跑一遍DFS,最后得到一个最大值,即为所求.
数组一定要开大!!!!
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <cstring> 5 #include <cstdlib> 6 #include <queue> 7 #include <stack> 8 #include <algorithm> 9 #define Max 1000012 10 #define re register 11 struct tree 12 { 13 int next,to,dis; 14 }t[Max]; 15 int cnt,n,ans=0,node,head[Max],dis[Max]; 16 bool vis[Max]={0}; 17 void add(int u,int v,int w) 18 { 19 t[++cnt].next=head[u]; 20 t[cnt].to=v; 21 t[cnt].dis=1; 22 head[u]=cnt; 23 } 24 void dfs(int x,int p) 25 { 26 for(re int i = head[x] ; i ; i = t[i].next) { 27 int v = t[i].to; 28 if(vis[v]) continue; 29 vis[v]=1; 30 dis[v] = p + t[i].dis; 31 if(dis[v] > ans) { 32 ans=dis[v]; 33 node=v; 34 } 35 dfs(v,dis[v]); 36 } 37 } 38 int main() 39 { 40 scanf("%d",&n); 41 int x,y; 42 for(re int i = 1 ; i <= n ; ++ i) { 43 scanf("%d%d",&x,&y); 44 if(y!=0) 45 add(i,y,1),add(y,i,1); 46 if(x!=0) 47 add(i,x,1);add(x,i,1); 48 } 49 memset(dis,0,sizeof dis); 50 dfs(1,0); 51 memset(vis,0,sizeof vis); 52 ans=0; 53 dfs(node,0); 54 printf("%d",ans); 55 return 0; 56 }
