洛谷 P4552 [Poetize6] IncDec Sequence

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

- 深度：4
- 宽度：4
- 结点8和6之间的距离：8
- 结点7和6之间的距离：3

其中宽度表示二叉树上同一层最多的结点个数，节点u, v之间的距离表示从u到v的最短有向路径上向根节点的边数的两倍加上叶节点的边数。

输入格式

第一行是一个整数，表示树的结点个数n。
接下来n-1行，每行两个整数u, v，表示树上存在一条连接u, v的边。
最后一行有两个整数x, y，表示求x, y之间的距离。

输出格式
输出三行，每行一个整数，依次表示二叉树的深度、宽度和x,y之间的距离。

输入输出样例
输入#1

10
4
1 2
4
1 3
8
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6

复制
输出#1
 

4
4
8

说明/提示
对于全部的测试点，保证1 ≤ u, v, x, y ≤ n ≤ 100，且给出的是一棵树。保证u是v的父结点。

思路：

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e4+10;
int head[2*N],deepth[2*N],width[2*N],max_deep = -1e9,deep = 1,max_wide = -1e9,tot;
bool vis[2*N];
struct Edge{int next;int to;int w;
}e[N*2];
void add_1(int u,int v,int w)
{tot++;e[tot].next = head[u];e[tot].to = v;e[tot].w = w;head[u] = tot;
}
void add_2(int u,int v,int w)
{tot++;e[tot].next = head[u];e[tot].to = v;e[tot].w = w;head[u] = tot;
}
void dfs(int x, int depth)
{if (vis[x]) return;vis[x] = true;max_deep = max(max_deep, depth);/*  for (int i = head[x]; i != -1; i = e[i].next){int to = e[i].to;dfs(to, depth + 1); // 递归调用时深度加1}*/int u = head[x];while(u != -1){int to = e[u].to;dfs(to,depth + 1);u = e[u].next;}
}
int main() 
{int n;cin >> n;memset(head,-1,sizeof(head));for(int i = 1 ; i <= n-1 ; i++){int u,v;cin >> u >> v;//有向图 add_1(u,v,1);add_2(v,u,2);}dfs(1,1);cout << max_deep;return 0;
}