1007. Message_Passing
Brief description:
… 给定一个无向图，每一个人初始有一个信息，每一步，可以选择一个人将它所知的所有信息告诉给与她相邻的另一个人。
。。要使得最后每个人都获得所有人的信息，最少需要多少步，满足最少步数条件下，有多少种不同的方案。
Analysis:
容易发现信息一定是先到一个汇点，再从这个汇点分发出去。。
设 F[u] 表示以 u 为根的子树，汇聚到 u 点时的方案数。
void dfs0(int u){
F[u] = sz[u] = 1; int cur = 0; REP_G(i, u){
del(i^1), dfs0(v);
sz[u] += sz[v], cur += sz[v];
F[u] *= F[v] * C(cur, sz[v]);
}
}
设 P[u] 表示 u 为根的子树外，汇聚到 u 点时的方案数。
。。于是可以通过另一个 dfs1() 过程，来避免枚举这个汇点。
void dfs1(int u){
res += sqr(P[u] * F[u] * C(n-1, sz[u]-1));
REP_G(i, u){
P[v] = P[u] * F[u] * C(n-sz[v]-1, n-sz[u]) / (F[v] * C(sz[u]-1, sz[v]));
//cout << v << " " << F[v] << " " << P[v] << " "<< C(n-1, sz[v]-1) << endl;
dfs1(v);
}
}
https://gist.github.com/lychees/6187521#file-message_passing-cpp
赛后膜拜了 wzk 巨巨的代码。。。才注意到中间的 dp 过程可以化简。。
。。。以 u 为汇点时。。方案数就是。。。 $$n!/\prod{{sz}_i}$$。。（。就是 有向树 的拓扑排序方案计数。。
。。于是就变得非常好写了。。。
https://gist.github.com/lychees/6187521#file-message_passing2-cpp
External link:
。。。
