题意:给出一棵树,现在你可以将其定向,记 \(d(u,v)\) 为从 \(u\) 到 \(v\) 需要逆多少条边才能走到。记 \(D\) 为所有的定向方式的 \(\max d(u,v)\),问有多少颗树 \(\max d(u,v)\) 等于 \(D\)。\(n\le 1000\)。
做法:
首先先考虑把 \(D\) 是多少直接弄出来,考虑直接取直径,假设长度为 \(l\),那么 \(D=\lfloor\frac{l+1}{2}\rfloor\)。并且容易构造,直接让奇数层往外,偶数层往里就可以练出来。
那么既然都这么取了,我们不妨也直接以直径中心为根去研究。首先有个很显然的 \(dp\),\(dp_{u,x,y}\) 代表子树中向下最大需要逆 \(x\) 条,向上最大逆 \(y\) 条的方案数,转移直接枚举两颗子树之间的限制就可以,但是这样复杂度太高了,大概是 \(O(n^4)\) 的。
发现其实我们转移的时候需要处理子树间的限制,这样太麻烦了,我们先转化一下,考虑更简单地表示 \(d(u,v)\)。记 \(h_u\) 代表 \(u\) 向根走的边数减去向下的边数的差,则 \(d(u,v)=\frac{|h_u-h_v|+\operatorname{dis}(u,v)}{2}\)。先不妨设直径长度为 \(2D\),则 \(|h_u-h_v|\le 2D-\operatorname{dis}(u,v)\)。
然后我们考虑得极端一点,假设 \(u,v\) 出于根的不同的子树,那么会有 \(|h_u|\le D-dep_u\)。同时我们再考虑可以相同子树的 \(u,v\),会发现 \(|h_u-h_v|\le |h_u|+|h_v|\le 2D-dep_u-dep_v\le 2D - \operatorname{dis}(u,v)\),发现这样我们就可以完全不用管子树间的限制了!
此时因为一组合法的 \(h\) 即对应一颗树,所以我们只需要 dp 这个 \(h\) 数组就可以了,因为我们直接选取了直径中点为根,所以要求叶子节点的 \(h\) 全部相同。并且这个 \(h\) 数组限制相当少,只要满足 \(|h_u|\le D-dep_u,|h_u-h_v|=1\) 即可,直接记 \(dp_{u,i}\) 代表 \(h_u=i\) 的情况即可。
做到这里还有一个问题,前面也提到我们假设的直径长度为 \(2D\),但是也有可能直径中点落在边上,假设在 \((s, t)\) 上,那么就是有一侧的满足 \(|h_u|\le D-dep_u,\) 另一侧满足 \(|h_u|\le D+1-dep_u\),并不需要全部的叶子节点都相同。但是这里有个问题,注意到相邻两层间的 \(h_u\) 奇偶性不同,所以直接按这个 dp 可能会出现两侧叶子节点都是偶数这种情况,这种情况我们最后再容斥一下减掉就可以了。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1050, N = 505, mod = 1e9 + 7;
int n, a[maxn], b[maxn];
vector<int> e[maxn];
int dep[maxn], pth[maxn], tot, f[maxn];
void dfs1(int u, int fa) {dep[u] = dep[fa] + 1; f[u] = fa;for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;dfs1(v, u);}
}
int dp[maxn][maxn];
void dfs2(int u, int fa, int d, int op) {for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;dep[v] = dep[u] + 1;dfs2(v, u, d, op);}int l = dep[u] - d + N + op, r = d - dep[u] + N + op;for (int i = l; i <= r; i++) {dp[u][i] = 1;for (int j = 0; j < e[u].size(); j++) {int v = e[u][j];if(v == fa)continue;dp[u][i] = dp[u][i] * (dp[v][i - 1] + dp[v][i + 1]) % mod;} }
}
int cal(int s, int t, int d, int op) {memset(dp, 0, sizeof(dp));dep[s] = dep[t] = 0;if(!op)dfs2(s, t, d + 1, 0), dfs2(t, s, d, 0);elsedfs2(s, t, d, 0), dfs2(t, s, d, 1);int ans = 0;for (int i = 1; i <= 2 * N; i++)ans = (ans + dp[s][i] * (dp[t][i - 1] + dp[t][i + 1]) % mod) % mod;return ans;
}
signed main() {cin >> n;if(n == 2) {cout << 2 << endl;return 0;}for (int i = 1; i < n; i++) cin >> a[i] >> b[i], e[a[i]].push_back(b[i]),e[b[i]].push_back(a[i]);dfs1(1, 0);int nw = 0;for (int i = 1; i <= n; i++)if(dep[nw] < dep[i])nw = i;dfs1(nw, 0);int pos = 0;for (int i = 1; i <= n; i++)if(dep[pos] < dep[i])pos = i;while(pos)pth[++tot] = pos, pos = f[pos];if(tot % 2 == 1) {int pos = pth[tot / 2 + 1];dep[pos] = 0, dfs2(pos, 0, tot / 2, 0);int ans = 0;for (int i = 1; i <= 2 * N; i++)ans = (ans + dp[pos][i]) % mod;cout << ans << endl;}else {int s = pth[tot / 2], t = pth[tot / 2 + 1], d = tot / 2 - 1;cout << (cal(s, t, d, 0) + cal(t, s, d, 0) - cal(s, t, d, 1) - cal(t, s, d, 1) + 2 * mod) % mod << endl;}return 0;
}