HDU - 4809 树形dp

找了半天bug 发现把q打成了p。。。

思路：用dp[ i ][ j ][ k ] 表示在 i 这个点 这个点的状态为 j （0：不选 1：属于奇联通块 2：属于偶联通块） 且 奇联通块 - 偶联通块 = k 的方案数， 这个统计的方案数不包括i这个点的联通块。

dp[u][0][x+y]=dp[u][0][x]*dp[v][0][y]+dp[u][0][x]*dp[v][1][y-1]+dp[u][0][x]*dp[v][2][y+1]

dp[u][1][x+y]=dp[u][1][x]*dp[v][0][y]+dp[u][1][x]*dp[v][2][y]+dp[u][2][x]*dp[v][1][y]

dp[u][2][x+y]=dp[u][2][x]*dp[v][0][y]+dp[u][1][x]*dp[v][1][y]+dp[u][2][x]*dp[v][2][y]

 #include<bits/stdc++.h>

 #define LL long long

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define piii pair<int, pair<int,int> >

 using namespace std;

 const int N =  + ;

 const int M =  + ;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const int mod = 1e9 + ;

 const int zero = ;

 int n, dp[N][][], tmp[][], down[N], up[N];

 vector<int> edge[N];

 void inline add(int &x, int y) {

     x += y; if(x >= mod) x -= mod;

 }

 void dfs(int u, int p) {

     dp[u][][zero] = ;

     dp[u][][zero] = ;

     up[u] = down[u] = ;

     for(int v : edge[u]) {

         if(v == p) continue;

         dfs(v, u);

         memset(tmp, , sizeof(tmp));

         for(int p = down[u]; p <= up[u]; p++) {

             for(int q = down[v] - ; q <= up[v] + ; q++) {

                 if((p + q > n) || (p + q < (-n) /  - )) continue;

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero-] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero+] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero] % mod);

                 add(tmp[][p+q+zero], 1ll * dp[u][][p+zero] * dp[v][][q+zero] % mod);

                 if(tmp[][p + q + zero]) down[u] = min(down[u], p + q), up[u] = max(up[u], p + q);

                 if(tmp[][p + q + zero]) down[u] = min(down[u], p + q), up[u] = max(up[u], p + q);

                 if(tmp[][p + q + zero]) down[u] = min(down[u], p + q), up[u] = max(up[u], p + q);

             }

         }

         for(int i = down[u]; i <= up[u]; i++)

             for(int j = ; j < ; j++)

                 dp[u][j][i + zero] = tmp[j][i + zero];

     }

 }

 void init() {

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

         edge[i].clear();

     memset(dp, , sizeof(dp));

 }

 int main() {

     while(scanf("%d", &n) != EOF) {

         init();

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

             int u, v; scanf("%d%d", &u, &v);

             edge[u].push_back(v);

             edge[v].push_back(u);

         }

         dfs(, );

         int ans = ;

         for(int i = down[]; i <= up[]; i++) {

             add(ans, 1ll * max(, i) * dp[][][i + zero] % mod);

             add(ans, 1ll * max(, i + ) * dp[][][i + zero] % mod);

             add(ans, 1ll * max(, i - ) * dp[][][i + zero] % mod);

         }

         add(ans,  * ans % mod);

         printf("%d\n", ans);

     }

     return ;

 }

 /*

 */