BZOJ2314 士兵的放置

树形DP，恩然后就不会了。。。

先写了个错的离谱程序。。。果然WA了

然后开始乱搞，欸，对了！

令f[i], g[i], h[i]分别表示i号节点自己放士兵，被儿子上的士兵控制，不被儿子上的士兵控制但被父亲上的士兵控制的情况下，以i为子树中最少的士兵数

F[i], G[i], H[i]表示对应的方案数，然后这方程写的沁人心脾。。。看程序吧

 /**************************************************************

     Problem: 2314

     User: rausen

     Language: C++

     Result: Accepted

     Time:3224 ms

     Memory:99512 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int N = 5e5 + ;

 const int inf = 1e9;

 const int mod = ;

 const int Maxlen = N * ;

 struct edge {

     int next, to;

     edge() {}

     edge(int _n, int _t) : next(_n), to(_t) {}

 } e[N << ];

 int n;

 int first[N], tot;

 ll f[N], g[N], h[N];

 ll F[N], G[N], H[N];

 ll ans;

 bool vis[N];

 char buf[Maxlen], *c = buf;

 int Len;

 inline int read() {

     int x = ;

     while (*c < '' || '' < *c) ++c;

     while ('' <= *c && *c <= '')

         x = x *  + *c - '', ++c;

     return x;

 }

 inline void Add_Edges(int x, int y) {

     e[++tot] = edge(first[x], y), first[x] = tot;

     e[++tot] = edge(first[y], x), first[y] = tot;

 }

 #define y e[x].to

 void dfs(int p) {

     int x, mn;

     ll t;

     vis[p] = ;

     f[p] = , g[p] = inf, h[p] = ;

     F[p] = G[p] = H[p] = ;

     for (x = first[p]; x; x = e[x].next)

         if (!vis[y]) {

             dfs(y);

             mn = min(min(f[y], g[y]), h[y]), t = ;

             if (f[y] == mn) t += F[y];

             if (g[y] == mn) t += G[y];

             if (h[y] == mn) t += H[y];

             f[p] += mn, (F[p] *= t) %= mod;

             mn = min(min(g[p] + f[y], g[p] + g[y]), h[p] + f[y]), t = ;

             if (g[p] + f[y] == mn) t += G[p] * F[y];

             if (g[p] + g[y] == mn) t += G[p] * G[y];

             if (h[p] + f[y] == mn) t += H[p] * F[y];

             g[p] = mn, G[p] = t % mod;

             h[p] += g[y], (H[p] *= G[y]) %= mod;

         }

 }

 #undef y

 int main() {

     Len = fread(c, , Maxlen, stdin);

     buf[Len] = '\0';

     int i, x, y;

     n = read();

     for (i = ; i < n; ++i) {

         x = read(), y = read();

         Add_Edges(x, y);

     }

     dfs();

     printf("%lld\n", min(f[], g[]));

     printf("%lld\n", f[] == g[] ? (F[] + G[]) % mod : f[] < g[] ? F[] : G[]);

     return ;

 }