Party at Hali

之前一直对树上动态规划不太感冒

这道题总算是对树上的动态规划的敲门砖吧

对这类题的理解又加深了许多，收获很大

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<assert.h>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<sstream>
#include<stack>
#include<queue>
#include<string>
#include<bitset>
#include<algorithm>
#pragma warning(disable:4996)
#define me(s)  memset(s,0,sizeof(s))
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int maxn = 200 + 10;
int d[maxn][2], f[maxn][2], n;
vector<int> sons[maxn];
int t;
map<string, int> dict;
int ID(string s)
{if (!dict.count(s)) dict[s] = t++;return dict[s];
}
int dp(int u, int k)
{f[u][k] = 1;d[u][k] = k;for (int i = 0; i < sons[u].size(); i++) {int v = sons[u][i];if (k) {d[u][k] += dp(v, 0);if (!f[v][0]) f[u][k] = 0;}else {d[u][k] += max(dp(v, 1), dp(v, 0));if (d[v][0] == d[v][1]) f[u][k] = 0;if (d[v][1] > d[v][0] && !f[v][1]) f[u][k] = 0;if (d[v][0] > d[v][1] && !f[v][0]) f[u][k] = 0;}}return d[u][k];
}
int main()
{string s, s2;while (cin >> n >> s){t = 0;dict.clear();for (int i = 0; i < n; i++) sons[i].clear();ID(s);                                           //先给老板分配0编号，因为不一定先输入老板的儿子节点for (int i = 0; i < n - 1; i++){cin >> s2 >> s;sons[ID(s)].push_back(ID(s2));}printf("%d ", max(dp(0, 0), dp(0, 1)));bool unique = false;if (d[0][0] > d[0][1] && f[0][0]) unique = true;if (d[0][1] > d[0][0] && f[0][1]) unique = true;if (unique) printf("Yes\n"); else printf("No\n");}
}