Posted on 2010-08-15 20:42
acronix 阅读(332)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：给你一棵树，求最长的路程及其数目。
分析： 这道题做的我好辛苦啊，说是树形dp，我的理解此题其实是个树形递推（自顶向下使用递归实现自底向上的递推），唯一的记忆话就是标记访问过的节点，防止倒退。
理解了这个，还有一个难点，就是计数的问题：当有过某个节点有多个最大值时的计数；当子树有相同最大值的计数的补充。
总之，trick多多。还有本题可由任一节点开始递归，并不影响树的性质，倒是要注意第二种计数情况！！
#include <cstdio>
#include <stdlib.h>
const int MAX = 10010;
struct Point{
int id,len;
struct Point *next;
} p[2*MAX],*head[MAX];
struct Recd{
bool flag;//标记
int max,num; //当前节点以下的所有最大值及数目
int max_rout;//以此节点为端点的最大值
int max_num; //以此节点为端点的最大值的数目
} a[MAX]; //记录各顶点的状态
int n,x,y,v,cnt;
inline void addedge(int x,int y,int v)//用邻接表把各节点串起来
{
cnt ++;
p[cnt].id = y;
p[cnt].len = v;
p[cnt].next = head[x];
head[x] = &p[cnt];
}
void dp(int root)
{
a[root].flag = true;
struct Point *q = head[root];
int m[2] = {0,0};
int m_cnt[2] = {1,1};
bool mark = false;
int son_max = -1 , son_num = 0;
int tnum[2] = {0,0};
while (q)
{
if (a[q->id].flag == true)//已访问过
{
q = q->next;
continue;
}
dp(q->id);
x = a[q->id].max_rout + q->len;
y = a[q->id].max_num;
if (x > m[0])
{
mark = false;
m[1] = m[0];
m_cnt[1] = m_cnt[0];
m[0] = x;
m_cnt[0] = y;
tnum[0] = 0; //pay attention
}
else if (x == m[0])
{
mark = true;
tnum[0] += m_cnt[0]*y;
m_cnt[0] += y;
}
else if (x > m[1])
{
m[1] = x;
m_cnt[1] = y;
}
else if(x == m[1])
{
m_cnt[1] += y;
}
if (son_max < a[q->id].max)
{
son_max = a[q->id].max;
son_num = a[q->id].num;
}
else if (son_max == a[q->id].max)
son_num += a[q->id].num;
q = q->next;
}
int temp ,sum;
if (mark)
{
sum = tnum[0];
temp = 2*m[0];
}
else {
temp = m[0] + m[1];
sum = m_cnt[0] * m_cnt[1];
}
if (temp < son_max)
{
temp = son_max;
sum = son_num;
}
else if (temp == son_max)//pay attention
{
sum += son_num;
}
a[root].max_rout = m[0];
a[root].max_num = m_cnt[0];
a[root].max = temp;
a[root].num = sum;
}
int main()
{
while (scanf("%d",&n) != EOF)
{
for (int i = 1; i <= n; i++)
{
a[i].flag = false;
head[i] = NULL;
}
cnt = 0;
for (int i = 1; i < n; i++)
{
scanf("%d %d %d",&x,&y,&v);
addedge(x,y,v);
addedge(y,x,v);
}
dp(1);
printf("%d %d\n",a[1].max,a[1].num);
}
return 0;
}