某島

… : "…アッカリ~ン . .. . " .. .
August 9, 2013

2013 Multi-University Training Contest 6

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:

。。。