题意：求树上每一点到其他任意点的最远距离。
题解：树形DP +树的直径的性质。树上一点到树的任意点的最远距离一定是到树的直径的2个端点中的某个点的距离，如若不然，会存在一个比直径更长的路径。因此找到树的一个直径后，答案便迎刃而解。
#include <cstdio>
#include <cstring>
#define max(a,b) (a>b?a:b)
const int maxn=10005;
struct Edge {
int v,next,w;
}edge[maxn*2];
int head[maxn],cnt;
void addedge(int u , int v , int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
///
int dp[maxn] , dp1[maxn],n;
int *node;
void dfs (int u)
{
for (int p=head[u] ; ~p ; p=edge[p].next)
{
int v=edge[p].v;
if(~node[v])continue;
node[v]=node[u]+edge[p].w;
dfs(v);
}
}
int main ()
{
int u,w;
while (~scanf("%d",&n))
{
memset (head , -1 , sizeof(head));
cnt=0;
int maxdis=0,maxu=1,maxv=1;
for (int i=2 ; i<=n ; ++i)
{
scanf("%d%d",&u,&w);
addedge (u , i , w);
addedge (i , u , w);
}
memset (dp , -1 , sizeof(dp));
memset (dp1 , -1 , sizeof(dp1));
node=dp;
dp[1]=0;
dfs(1);
for (int i=1 ; i<=n ; ++i)
{
if(dp[i]>maxdis)
{
maxdis=dp[i];
maxu=i;
}
}
memset (dp , -1 , sizeof(dp));
node=dp;
dp[maxu]=0;
dfs(maxu);
maxdis=0;
for (int i=1 ; i<=n ; ++i)
{
if(dp[i]>maxdis)
{
maxdis=dp[i];
maxv=i;
}
}
node=dp1;
dp1[maxv]=0;
dfs(maxv);
for (int i=1 ; i<=n ; ++i)
{
printf("%d\n",max(dp[i],dp1[i]));
}
}
return 0;
}
HDU 1520 Anniversary party
///4881889 2011-11-02 17:10:07 Accepted 1520 46MS 388K 1514 B C++ Geners
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=6005;
int dp[maxn][2];
///第i个点选和不选的最大值；
int node[maxn];
bool son[maxn];
struct Edge {
int v,next;
}edge[maxn];
int head[maxn], cnt;
void addedge(int u, int v)
{
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void dfs (int u)
{
dp[u][0]=node[u];
dp[u][1]=0;
//printf("%d %d\n", u, head[u]);
for (int p=head[u] ; ~p ; p=edge[p].next)
{
const int & v=edge[p].v;
//printf("u==%d v==%d\n",u, v);
dfs(v);
dp[u][0]+=dp[v][1];
dp[u][1]+=max(dp[v][1], dp[v][0]);
}
}
int main ()
{
int n, u, v;
while (~scanf("%d", &n))
{
memset (head, -1, sizeof(head));
cnt=0;
memset (son, false, sizeof(son));
for (int i=0 ; i<n ; ++i)
{
scanf("%d", node+i);
}
for (int i=0 ; i<n ; ++i)
{
scanf("%d%d", &u, &v);
if((!u) && (!v))break;
u--,v--;
addedge(v,u);
son[u]=true;
}
for (int i=0 ; i<n ; ++i)
{
if(!son[i])dfs(i);
}
int ans=0;
for (int i=0 ; i<n ; ++i)
{
//printf("%d %d\n", dp[i][0], dp[i][1]);
ans=max(ans, dp[i][0]);
ans=max(ans, dp[i][1]);
}
printf("%d\n", ans);
}
return 0;
}
POJ 1655 树的重心，求树上一点，以它为根时，它的所有子树的结点最大值最小
#include <cstdio>
#include <cstring>
#include <algorithm>
///树的重心，对于拆分树的分治递归算法里，有很好的优化作用
using namespace std;
const int maxn=20000+123;
const int inf=0x3fffffff;
struct Edge {
int v,next;
}edge[maxn*2];///若存储无向边，边集数组开两倍大小
int head[maxn], cnt;
void addedge(int u, int v)
{
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int sum[maxn], max_son[maxn];
void init ()
{
cnt=0;
memset (head, -1, sizeof(head));
memset (sum, 0, sizeof(sum));
memset (max_son, 0, sizeof(max_son));
}
int n;
void dfs(int u, int past)
{
sum[u]=1;
for (int p=head[u] ; ~p ; p=edge[p].next)
{
int v=edge[p].v;
if(v!=past)
{
dfs(v, u);
sum[u]+=sum[v];
max_son[u]=max(sum[v], max_son[u]);
}
}
max_son[u]=max(max_son[u], n-sum[u]);
}
int center, ans;
void get_bary()
{
dfs(1, 0);
ans=inf;
for (int i=1 ; i<=n ; ++i)
{
if(max_son[i]<ans)
{
ans=max_son[center=i];
}
}
}
int main ()
{
int cas;
int u, v;
scanf("%d", &cas);
while (cas--)
{
init();
scanf("%d", &n);
for (int i=1 ; i<n ; ++i)
{
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
get_bary();
printf("%d %d\n", center, ans);
}
return 0;
}
/*
2
7
2 6
1 2
1 4
4 5
3 7
3 1
12
2 6
1 2
1 4
4 5
3 7
3 2
7 8
9 10
10 11
11 12
6 9
13
2 6
1 6
1 4
6 5
3 7
3 2
7 8
9 10
10 11
11 12
6 9
6 13
*/