HDU 6446 -- Tree and Permutation
题目链接：HDU 6446 -- Tree and Permutation
题意：
给出一棵带有N个节点的树以及每条边的权值，N个节点的全排列有N!种，令Pi,j表示第i个排列第j个位置的节点，从Pi,1开始，按照第i个排列的顺序，依次按树上的最短路径走到下一个节点，直到到达Pi,N，记从Pi,1走到Pi,N的总长度为D(Pi)，求：$ sum_{i=1}^{N!}{D(P_i)} $
解析：
- 对每条边单独计算贡献，一条边E将树分成两侧，假设其中一侧大小(子树规模)为M，则另一侧大小为N - M。
- 在N!条路线中每条路线都分为N-1段，对每段单独计算贡献，例如某一段从X到Y，则该段经过E当且仅当X与Y分别在E的两侧，显然这样的(X, Y)有序点对共有2M(N-M)对，除了X，Y这两个节点外的其他N-2个节点能够形成(N-2)!种排列，所以E在这一段有所贡献的排列数为2M(N-M)(N-2)!。
- 共有N-1段，设E的长度为L，则E的贡献为2LM(N-M)(N-1)!。
至于如何求每个E对应的M，完全就是求树上每棵子树的规模，dfs即可在O(n)时间内处理出来，所以这题是大水题可做的简单题。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 100010;
const int mod = 1e9 + 7;
struct edge
{
int to, len;
};
vector<edge> vec[maxn];
long long f[maxn], ans;
int n;
// 参数为当前节点、当前节点的父亲节点，函数返回以当前节点为根的子树规模
int dfs(int v, int fa) {
int siz = 1;
for (int i = 0; i < vec[v].size(); i++) {
if (vec[v][i].to == fa) continue;
int siz2 = dfs(vec[v][i].to, v);
siz += siz2;
ans = (ans + 1ll * vec[v][i].len * siz2 % mod * (n - siz2) % mod * f[n-1] % mod * 2) % mod;
}
return siz;
}
int main() {
f[0] = 0, f[1] = 1;
for (int i = 2; i < maxn; i++) f[i] = f[i-1] * i % mod;
while (~scanf("%d", &n)) {
ans = 0;
for (int i = 0; i <= n; i++) vec[i].clear();
for (int i = 0; i < n - 1; i++) {
int v;
edge e;
scanf("%d %d %d", &v, &e.to, &e.len);
vec[v].push_back(e);
swap(v, e.to);
vec[v].push_back(e);
}
dfs(1, 0);
printf("%lld
", ans);
}
return 0;
}
比赛时没想到dfs求子树规模的写法，想了一个拓扑排序写法，但用到了map映射，时间复杂度变为O(NlogN)，遭到无情TLE，赛后优化掉了map，代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 100010;
const int mod = 1e9 + 7;
struct edge
{
int to, len;
};
int deg[maxn]; // 节点的度
int num[maxn]; // 按拓扑序列添加边，有多少节点与当前节点相通
int rec[maxn]; // rec[i]表示i这个节点已经处理了rec[i]条邻接边
bool vis[maxn]; // 记录节点是否进入过队列
long long f[maxn]; // 阶乘
vector<edge> vec[maxn]; // 邻接表
queue<int> que; // 拓扑排序的队列
long long bfs(int n) {
while (!que.empty()) que.pop();
for (int i = 1; i <= n; i++) if (deg[i] == 1) que.push(i), vis[i] = true;
long long ans = 0;
while (!que.empty()) {
int x = que.front(); que.pop();
for (int i = 0; i < vec[x].size(); i++) {
int tmp = vec[x][i].to;
if (!vis[tmp]) num[tmp] += num[x];
if (--deg[tmp] == 0 && rec[tmp] != vec[tmp].size()) {
ans = (ans + 1ll * vec[x][i].len * num[tmp] % mod * (n - num[tmp]) % mod * f[n-1] % mod * 2) % mod;
rec[x]++, rec[tmp]++;
}
if (deg[tmp] == 1) {
que.push(tmp);
vis[tmp] = true;
}
}
}
return ans;
}
int main() {
int n;
f[0] = 0, f[1] = 1;
for (int i = 2; i < maxn; i++) f[i] = f[i-1] * i % mod;
while (~scanf("%d", &n)) {
memset(deg, 0, sizeof(deg));
memset(rec, 0, sizeof(rec));
memset(vis, false, sizeof(vis));
for (int i = 0; i <= n; i++) {
vec[i].clear();
num[i] = 1;
}
for (int i = 0; i < n - 1; i++) {
int u;
edge no;
scanf("%d %d %d", &u, &no.to, &no.len);
vec[u].push_back(no);
deg[u]++;
swap(no.to, u);
vec[u].push_back(no);
deg[u]++;
}
printf("%lld
", bfs(n));
}
return 0;
}
比赛时队友提出一个公式，设sum为两两点对之间的最短距离总和，公式简化后为2(N-1)!sum
当时以为求sum需要知道所有点对之间的距离，用Floyd算法显然是超时超内存的。但对比两个公式可以发现sum=LM(N-M)，也就是计算每条边对sum的贡献即可，不需要知道所有点对之间的距离。代码实现是跟上面dfs一样的写法。