树形DP考点很多，状态转移有时会很复杂，但是也有规律可寻，最重要的是抓住父子关系之间的状态转移。
-
树的最大独立集：尽量选择多的点，使得任何两个结点均不相邻。
状态转移，两种方案：
这样用记忆化的方案来做。
另一种，也是很常见的，也是很重要的——刷表法。
计算出一个 后，去刷新他的父亲，和祖父结点的值。
-
树的重心：找到一个点，以这个点为重心，最大子树的结点数最小。
这里需要反选，名字瞎起的，也很常见的哦~，
-
树的直径，也可以用树形DP来做，但是两次DFS更常用。
-
树形背包。
推荐题目：树形DP很具有思维和编程控制能力，题目较多，认真思考。
BZOJ 3722，1131，4753
Description
Fancy爷宣布XJOI群将要选举下一任群主。候选人有两名，分别是XYW和吉丽。共有n个人（从1~n编号）参加这次投票。他们之间形成了一个树结构，根结点（1号结点）为Fancy。树上的结点有两种身份：专家（叶子结点）或领导（非叶子结点）。每位专家都有自己的选择——支持XYW和吉丽之中的一个；每位领导都有若干个下属（儿子结点），领导的选择决定于下属中人数较多的那一方，下属的数目保证为奇数，从而不会出现平局状况。最后，Fancy的选择即为选举结果。吉丽和XYW知道，目前仍有一些专家处于犹豫未决的状态，只要前去游说，就可获得他的支持。但是由于精力不够，每人每天只能选择游说1名专家；XYW起床更早，他比吉丽先进行游说。这样两人交替进行，直到每位专家都有了确定的选择。请问XYW是否有策略保证自己赢得选举胜利？
Input
第一行一个整数n(2<=n<=1000)，表示人数。接下来有n行。第i行中，第一个数为c。如果c[i]<=0，则i是专家，-2表示其支持XYW，-1表示支持吉丽，0表示仍在犹豫；如果c[i]>0，则c[i]为奇数，表示i是领导，其后c[i]个整数为i的下属。（数据保证为树结构，即除了根节点1以外每个结点有且仅有一个上级）
Output
若XYW无法保证胜利，仅输出一行NIE。否则，输出第一行包含TAK和一个非负整数d；输出第二行包含d个整数，按升序排列，表示XYW在必胜策略下，第一天可以选择游说的专家的编号。（如果不存在犹豫不决的专家，且XYW获得胜利的情况下，则d=0，第二行为空行）
Sample Input
43 2 3 4-20-1
Sample Output
TAK 13
HINT
乍一眼看去，很是复杂，树形博弈SG函数，挺麻烦的，但是数据量很小，考虑枚举O(n^2)。
枚举每一个犹豫的人，看是否必胜，统计贡献值即可~
#include using namespace std; const int maxn = 1005; struct Edge { int to,next; }e[maxn*2]; int tot; int n; int c[maxn]; int head[maxn]; void add(int u,int v) { e[++tot].to = v; e[tot].next = head[u]; head[u] = tot; } int col[maxn]; int dfs(int u) { if(c[u]<=0) return col[u]; int sum = 0; for(int i = head[u]; i ; i = e[i].next) { int v = e[i].to; sum+=dfs(v); } if(sum<0) return -1; if(sum>0) return 1; return 0; } int main() { freopen("in.txt","r",stdin); scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&c[i]); for(int j = 1; j <= c[i]; j++) { int v; scanf("%d",&v); add(i,v); } if(c[i]==-2) col[i] = 1; if(c[i]==-1) col[i] = -1; if(c[i]==0) col[i] = 0;