题目：http://115.28.138.223/view.page?gpid=T24
题意就是让求树上的任意两个节点间的距离的最大值。就是树的直径。
首先树的直径模板转载自http://www.07net01.com/2015/08/908766.html
模板思路是先任意确定一个点a，加入到队列当中。然后对这个点用广搜找到和它距离最远的点b。然后用相同的方法对点b找距离它最远的点。这个距离就是要求的直径。
实现：因为求树的直径题目数据量往往比较大，所以用邻接表来储存数据；至于对两个端点的查找通过bfs实现，先将第一次选择的起点a队。 然后开始搜索与a连接的所有边，并将权值存入dis[]数组 dis[x]=dis[top]+edge[i].w（dis[x]指的是当前搜索到的点 与之前与它相连的搜索过边的总权值，dis[top]是指当前搜索到的点的之前与它相连的搜索过边的总权值，edge[i].w是点top到当前搜索到的点 的连线的权值）完成于对当前点的搜索后，将其入队，然后对下 一个点进行此操作，每次搜索时，同时将最大的权值存入sum中如此重复直至队列为空，这样这个搜素结束后，sum的值就是a点到距离其最远的点b的总权值之和；此时再以b为起点进行第二次搜索（第 二次搜 索步骤与第一次相同）
其实就是简单的邻接表应用。只是在下不太熟。于是，觉得很机智。。。。。
#include<stdio.h>
#include<iostream>
#include<string.h>
#define maxn 10010
using namespace std; int head[maxn*];
int vis[maxn*]; // 判断每个节点是否已经被访问过。
int dis[maxn*]; //存储每个节点到当前节点的路径长
int que[maxn*];
int edgeNum;
int n, m;
int ans;
int sum; struct Edge {
int v, c, nxt;
}edge[maxn*]; // T_T哭晕...居然三倍的会TLE...TLE... void addEdge(int a, int b, int c) {
edge[edgeNum].v = b;
edge[edgeNum].c = c;
edge[edgeNum].nxt = head[a];
head[a] = edgeNum++;
} void getMap() {
edgeNum = ;
memset(head, -, sizeof(head));
for (int i=; i<=n; ++i) {
int temp;
scanf("%d", &temp);
addEdge(temp, i, );
addEdge(i, temp, );
}
for (int i=; i<=m; ++i) {
int temp;
scanf("%d", &temp);
addEdge(temp, i+n, );
addEdge(i+n, temp, );
}
} void bfs(int num) {
memset(vis, , sizeof(vis));
memset(dis, , sizeof(dis));
ans = num;
sum = ;
int front = -, rear = ;
que[++front] = num;
while(front >= rear) {
int top = que[front--];
for (int i=head[top]; i!=-; i=edge[i].nxt) {
int v = edge[i].v;
if (!vis[v]) {
dis[v] = dis[top] + edge[i].c;
vis[v] = ;
que[++front] = v;
if (sum < dis[v]) {
sum = dis[v];
ans = v;
}
}
}
}
} int main() {
while(~scanf("%d%d", &n, &m)) {
getMap();
bfs();
bfs(ans);
printf("%d\n", sum);
}
return ;
}
还有某大神做的一种，转载自：http://www.cnblogs.com/hate13/p/4643573.html
用DP。求出每个点的和所有点之间的距离的最大值和第二大值。然后它们的和的最大值就是树的直径。
初始化父亲节点的两个距离都是0。然后如果子节点最大值+1大于父亲节点的最大值。更新父亲节点的两个值。否则如果子节点最大值+1大于父亲节点的第二大值。那么只更新第二大值就可以了。
更机智。有木有。。(⊙o⊙)…额。。还是在下水平低。。
#include<stdio.h>
#include<iostream>
#include<string.h>
#define maxn 10010
using namespace std; int head[maxn*];
int n, m;
int dp[maxn*][];
int edgeNum; struct Edge {
int v,nxt;
}edge[maxn*]; // T_T哭晕...居然三倍的会TLE...TLE... void addEdge(int a, int b) {
edge[edgeNum].v = b;
edge[edgeNum].nxt = head[a];
head[a] = edgeNum++;
} void getMap() {
edgeNum = ;
memset(head, -, sizeof(head));
for (int i=; i<=n; ++i) {
int temp;
scanf("%d", &temp);
addEdge(temp, i);
//addEdge(i, temp, 1);
}
for (int i=; i<=m; ++i) {
int temp;
scanf("%d", &temp);
addEdge(temp, i+n);
//addEdge(i+n, temp, 1);
}
} void dfs(int u) {
dp[u][] = dp[u][] = ;
for (int i=head[u]; i!=-; i=edge[i].nxt) {
int v = edge[i].v;
dfs(v);
if (dp[v][]+ >= dp[u][]) {
dp[u][] = dp[u][];
dp[u][] = dp[v][]+;
}
else if (dp[v][]+ > dp[u][]) {
dp[u][] = dp[v][]+;
}
}
} int main() {
while(~scanf("%d%d", &n, &m)) {
getMap();
dfs();
int sum = ;
for (int i=; i<=n+m; ++i) {
int temp = dp[i][] + dp[i][];
sum = max(temp, sum);
}
printf("%d\n", sum);
}
return ;
}