[FZU 2142 Center of a Tree] 树形DP

    xiaoxiao2025-02-04  14

    FZU 2142 Center of a Tree [树形DP]

    题目链接: [FZU 2142 Center of a Tree] 题意描述:一个顶点是一棵树的中心 当且仅当 从该点出发到树上其他节点距离最大的值最小, 可以证明中心最多不会超过两个。然后给定一个N个顶点的一棵树, 1 <= N <=1000。 要你求有多少棵子树,满足该子树的中心与原树的中心相同。 解题思路:首先, 求出中心点。求出树上每个点到树上其他节点的最大距离,然后就可以求出中心点。 这里可以用两次DFS解决。第一次DFS求出dist[u][1]和 dist[u][1] , 分别表示u 为根节点的子树上距离u最大距离和次大距离, 第二次DFS就是从跟节点出发,求出每个顶点在原树上能到达的最大距离和次大距离, 这个过程的方法跟  《[SGU - 149 Computer Network] 树形DP 求带权树上每个节点的最长路长度 》 一样。 然后,用dp[u][k] 表示 u 为根节点的子树上深度小于等于k 的方案数。这个可以通过一次DFS求出。而如果要求 深度为k 的方法数, 只需要 dp[u][k] - dp[u][k - 1] 即可。 然后,考虑中心点有两个的情况(用u和v表示这两个中心点),那么答案就是, ∑(dp[u][k] - dp[u][k - 1])*(dp[v][k] - dp[v][k - 1])。 考虑中心点只有一个的情况就复杂一些了。因为要保证至少有两个根节点的子节点的最大距离相同。求深度为k的方法数的时候,用F[i][0], F[i][1], F[i][2]表示当前深度k下根节点的前i个子节点的构成的子树深度为k 的子树个数为0, 1, 2及两个以上的方法数。 那么可以得到状态转移方程: F[i][0] = F[i - 1][0] * (1 + dp[v][k - 1]) % MOD; F[i][1] = F[i - 1][1] * (1 + dp[v][k - 1]) % MOD + F[i - 1][0] * (dp[v][k] - dp[v][k - 1]) % MOD; F[i][2] = F[i - 1][2] * (1 + dp[v][k - 1]) % MOD + (F[i - 1][1] + F[i - 1][2]) * (dp[v][k] - dp[v][k - 1]) % MOD; #include <queue> #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; //#pragma comment(linker, "/STACK:1024000000,1024000000") #define FIN freopen("input.txt","r",stdin) #define FOUT freopen("a.out","w",stdout) #define fst first #define snd second typedef __int64 LL; typedef pair<int, int> PII; const int MAXN = 1000 + 5; const int MOD = 10086; int T, N; struct Edge { int v, next; Edge() {} Edge (int v, int next) : v (v), next (next) {} } edges[MAXN << 1]; int head[MAXN], tot; PII ecc[MAXN]; int dp[MAXN][MAXN], dist[MAXN][2], S[MAXN], F[MAXN][3], SIZE; int P[MAXN]; void init() { tot = 0; memset (head, -1, sizeof (head) ); memset (dp, 0, sizeof (dp) ); P[0] = 1; for (int i = 1; i < MAXN; ++i) P[i] = (P[i - 1] << 1) % MOD; } void add_edge (int u, int v) { edges[tot] = Edge (v, head[u]); head[u] = tot ++; } void read() { int u, v; scanf ("%d", &N); for (int i = 1; i <= N - 1; i++) { scanf ("%d %d", &u, &v); add_edge (u, v); add_edge (v, u); } } void dfs1 (int u, int pre) { int v, temp; dist[u][1] = dist[u][0] = 1; for (int i = head[u]; ~i; i = edges[i].next) { v = edges[i].v; if (v == pre) continue; dfs1 (v, u); temp = dist[v][1] + 1; if (temp > dist[u][1]) swap (temp, dist[u][1]); if (temp > dist[u][0]) swap (temp, dist[u][0]); } } void dfs2 (int u, int pre) { int v, temp; for (int i = head[u]; ~i; i = edges[i].next) { v = edges[i].v; if (v == pre) continue; if (dist[u][1] == dist[v][1] + 1) { temp = dist[u][0] + 1; } else { temp = dist[u][1] + 1; } if (temp > dist[v][1]) swap (temp, dist[v][1]); if (temp > dist[v][0]) swap (temp, dist[v][0]); dfs2 (v, u); } } void dfs3 (int u, int pre) { int v; for (int k = 0; k <= N; k++) dp[u][k] = 1; for (int i = head[u]; ~i; i = edges[i].next) { v = edges[i].v; if (v == pre) continue; dfs3 (v, u); for (int k = 1; k <= N; k++) { dp[u][k] = (dp[u][k] + dp[u][k] * dp[v][k - 1] % MOD) % MOD; } } } void center() { dfs1 (1, -1); dfs2 (1, -1); for (int i = 1; i <= N; i++) { ecc[i] = PII (dist[i][1], i); } sort (ecc + 1, ecc + N + 1); } int solve() { int u, v, ans; u = ecc[1].snd, v = ecc[2].snd; if (N != 1 && ecc[1].fst == ecc[2].fst) { dfs3 (u, v); dfs3 (v, u); ans = 1; for (int k = 1; k <= N; k ++) { int x = dp[u][k] - dp[u][k - 1]; int y = dp[v][k] - dp[v][k - 1]; ans = (ans + x * y) % MOD; } } else { dfs3 (u, -1); ans = 1; int SIZE = 0; for (int i = head[u]; ~i; i = edges[i].next) { v = edges[i].v; S[++ SIZE] = v; } if (SIZE > 1) ans = ans + P[SIZE] - SIZE - 1; for (int k = 1; k <= N; k ++) { F[0][0] = 1, F[0][1] = F[0][2] = 0; for (int i = 1; i <= SIZE; i++) { v = S[i]; F[i][0] = F[i - 1][0] * (1 + dp[v][k - 1]) % MOD; F[i][1] = F[i - 1][1] * (1 + dp[v][k - 1]) % MOD + F[i - 1][0] * (dp[v][k] - dp[v][k - 1]) % MOD; F[i][2] = F[i - 1][2] * (1 + dp[v][k - 1]) % MOD + (F[i - 1][1] + F[i - 1][2]) * (dp[v][k] - dp[v][k - 1]) % MOD; F[i][1] %= MOD; F[i][2] %= MOD; } ans = (ans + F[SIZE][2]) % MOD; } } ans = (ans + MOD) % MOD; return ans; } int main() { #ifndef ONLINE_JUDGE FIN; // FOUT; #endif // ONLINE_JUDGE int cas = 0; int ans; scanf ("%d", &T); while (T --) { init(); read(); center(); ans = solve(); printf ("Case %d: %d\n", ++ cas, ans); } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-1296078.html
    最新回复(0)