这题有人归为树型DP，我看不像，至少没有决策枚举的过程，完全是个“树型递推”。稀疏图用邻接表存，然后DFS一下就变成树了。
　　Submit 1: WA on 1。实在没找到什么地方错了。
　　（重装系统时不小心把这题的解题手记和程序弄丢了，只好重写，以上内容是根据回忆写的，不保证准确）
　　Submit 2: RTE on 13。重写程序后，第一个点直接过了，因没有以前的程序，查不出为什么那个程序WA on 1了。但RTE也够奇怪的，查了一遍程序，没有发现有数组越界或者指针指向非法地址的问题。生成大数据测试。发现在n>15000时出现了RTE，而且是指针指向非法地址！一句一句的查发现，如下写法：(main()中) vertex vertexes[16000]; 数组的有些成员没有初始化！怀疑根本没有调用构造函数。
　　Submit 3: AC。
　　接受滕老师意见，仔细查为什么没有调用构造函数。当我自己写构造函数，而不让编译器合成时，没有出现对象没有初始化的现象。这就怪了，难道合成的构造函数与我写的构造函数有什么区别吗？

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

//AC
#include <cstdio>
#include <cstring>
using namespace std;
 
struct vertex;
 
struct edge
{
    vertex *u;
    edge *next;
};
 
struct vertex
{
   bool visited;
   long assonum,noc;
   edge *link;
   vertex():visited(0),assonum(0),noc(0),link(0){};
};
 
long n;
edge *rc;
 
void dfs(vertex *v)
{
    v->visited=true; v->noc=1;
    while (v->link)
    {
        if (!v->link->u->visited)
        {
            dfs(v->link->u);
            v->noc+=v->link->u->noc;
            v->assonum=v->link->u->noc > v->assonum ? v->link->u->noc : v->assonum;
        }
        rc=v->link; v->link=v->link->next;
        delete rc;
    }
    v->assonum=n-v->noc > v->assonum ? n-v->noc : v->assonum;
}
 
int main()
{
    vertex vertexes[16001];
    scanf("%ld",&n);
    for (long i(0),a,b;i<n-1;++i)
    {
        scanf("%ld %ld",&a,&b);
        edge *newedge=new edge;
        newedge->u=&vertexes[b];
        newedge->next=vertexes[a].link;
        vertexes[a].link=newedge;
        newedge=new edge;
        newedge->u=&vertexes[a];
        newedge->next=vertexes[b].link;
        vertexes[b].link=newedge;
    }
    dfs(&vertexes[1]);
    long min(16001),c(0);
    for (long i(1);i<=n;++i)
        if (vertexes[i].assonum<min)
        { 
            min=vertexes[i].assonum;  c=1;
        }
        else if (vertexes[i].assonum==min) ++c;
    printf("%ld %ld\n",min,c);
    for (long i(1);i<=n;++i)
        if (vertexes[i].assonum==min) printf("%ld ",i);
    printf("\n");
    return 0;
}