4.4 模拟赛 A

改不动 BC 了 /kel

签到失败。

题目链接

显然只需要考虑第一个点为 $1$ 的情况，其他情况的方案数量是一样的。

一个合法的排列等价于在树上走，走到一个点时可以标记它，除了 $1$ 每个点只被标记一次，从 $1$ 开始在 $1$ 结束， $1$ 在开始和结束时各被标记一次，且两次标记间的路径是简单路径。

我们考虑题目给的删完所有边权的条件，就是每个点被经过 $\frac{\sum_v w(u,v)}{2}$ 次。

对于每个点 $u$ 我们考虑这样构造一个序列 $S_u$

第一次到达点 $u$ 的时候，如果是从 $f$ 走来那么就加入 $f$ 。
如果标记这个点且这个点不是 $1$ 就在序列加入一个 $0$ 。
每次离开 $u$ 时加入这一步终点 $t$。

显然我们可以知道对于一个合法的行走， $S_u$ 长度是 $\frac{\sum_v w(u,v)} 2 + 1 + [u \neq 1]$ 。并且对于一种行走，对应了唯一一组 $\{S_u\}$ 。因为我们一旦拥有了这么一组 $\{S_u\}$ 就可以通过这个集合走出唯一一个行走方案来，而一个行走方案显然也能构造出唯一的集合。

我们考虑什么情况 $\{S_u\}$ 对应的行走是合法的，显然对于一条简单路径，每条边只能经过一次，所以这个时候这么构造的好处就出现了，我们会发现，一个序列 $S_u$ 中一定不能有相邻的相同的数字。一旦出现相邻相同的数字，就意味着走想这个点，并且没有标记这个点的情况下就走回去了。

同时对于 $u \neq 1$ 一个序列的开头结尾必须一致。显然你从哪条边走过来最终就必须同样地走回去。

这个东西可以容斥解决，我们考虑一种颜色有 $c$ 个，如果违反了 $i$ 个限制，相当于我们钦定 $i$ 对相邻的放在一起，方案数量为 $c-1\choose i$ ，系数为 $(-1)^i$ ，然后剩下了 $c-i$ 个与其他颜色的一起进行任意排列。

然后我们显然可以暴力。对于每个点暴力做，讨论一下开头结尾的 $f$ ，复杂度是 $O(n^3)$。

如何优化？

我们可以考虑 $f$ 单独拿出来，并且钦定它不违反限制，现在的容斥就变成了只选择儿子了。我们假设父亲有 $a$ 个，当前容斥的方案是对 $b$ 个数任意排列，那么这一步的方案是 $b!{b-1\choose a-2}$ 。

我们来分析一下为啥丢掉父亲复杂度就对了，显然某条边的权值不会超过子树 size 的两倍，所以我们只需要合并子树，复杂度是上次分析过的 $O(n^2)$。

感觉到现在为止写的东西都好感性啊。。还是来一点一点分析一下~~对着zjk代码写的~~代码吧。。（这种容斥真的zbl）。

void dfs( int u , int fa , int wf ) {
    int s;
    if( u != 1 ) dp[u][1] = 1 , s = 1; // currently only 0 in S_u
    else dp[u][0] = 1 , s = 0;
    for( auto& t : G[u] ) if( t.fi != fa ) {
        int v = t.fi;
        dfs( v , u , t.se / 2 );
        for( int i = 0 ; i <= s ; ++ i )
            for( int j = 1 ; j <= t.se / 2 ; ++ j ) { // j : the rest after merging
                ( td[i + j] += 1ll * dp[u][i] * C( t.se / 2 - 1 , t.se / 2 - j ) % P * iJ[j] % P * ( ( t.se / 2 - j & 1 ) ? P - 1 : 1 ) % P ) %= P;
            }
        for( int i = 0 ; i <= s + t.se ; ++ i ) dp[u][i] = td[i] , td[i] = 0;
        s += t.se / 2;
    }
    int re = 0;
    if( u == 1 ) {
        for( int i = 0 ; i <= s ; ++ i ) ( re += 1ll * J[i] % P * dp[u][i] % P ) %= P;
    } else {
        for( int i = wf ; i <= s ; ++ i )
            ( re += 1ll * J[i] % P * dp[u][i] % P * C( i - 1 , wf - 1 ) % P ) %= P;
    }
    res = 1ll * res * re % P;
}

这是一个主体的 dfs 。

$dp[u][i]$ 的定义是当前 $u$ 这个点的子树内，保留了 $i$ 个东西（用来任意排列），也就是说是已经合并了一些东西的。

首先是初始值

1
2
3

int s;
if( u != 1 ) dp[u][1] = 1 , s = 1; // currently only 0 in S_u
else dp[u][0] = 1 , s = 0;

这里，如果 $u \neq 1$ ，显然开始序列里面就有一个 $0$ 存在，所以 $dp[u][1] = 1$ ，如果 $u = 1$ 显然开始的时候序列里面啥都没有。

1
2
3

for( auto& t : G[u] ) if( t.fi != fa ) {
        int v = t.fi;
        dfs( v , u , t.se / 2 );

递归处理儿子，没啥好说的。

for( int i = 0 ; i <= s ; ++ i )
            for( int j = 1 ; j <= t.se / 2 ; ++ j ) { // j : the rest after merging
                ( td[i + j] += 1ll * dp[u][i] * C( t.se / 2 - 1 , t.se / 2 - j ) % P * iJ[j] % P * ( ( t.se / 2 - j & 1 ) ? P - 1 : 1 ) % P ) %= P;
            }
        for( int i = 0 ; i <= s + t.se ; ++ i ) dp[u][i] = td[i] , td[i] = 0;
        s += t.se / 2;

合并的过程。我们考虑在之前子树中保留了 $i$ 个，这个子树保留了 $j$ 个，显然 $i$ 应当从 $0$ 开始枚举，因为如果当前在 $1$ 的子树中是可能开始啥都没有的，然后 $j$ 应当从 $1$ 开始枚举，因为子树内不管怎么 merge 后，总是会剩下至少一个数（就算全部相邻，也还是会有一个数去任意放）。

然后转移，我们知道会有 t.se/2 个 $v$ 出现在最后的序列中，所以有 t.se / 2 - 1 个空位，如果想要保留 j 个数字，我们需要合并其中的 t.se / 2 - j 个位置。所以我们有 C( t.se / 2 - 1 , t.se / 2 - j ) 这个系数。然后容斥系数 ( ( t.se / 2 - j & 1 ) ? P - 1 : 1 ) 显然。最后考虑 $\frac 1 {j!}$ 这个东西。我们相当于剩下了 $j$ 个 $v$ 去任意排列，这 $j$ 个的相对顺序是不重要的，所以最后应当除以 $j!$ 。

然后是复制 dp 数组和更新 siz ，都不重要。

int re = 0;
    if( u == 1 ) {
        for( int i = 0 ; i <= s ; ++ i ) ( re += 1ll * J[i] % P * dp[u][i] % P ) %= P;
    } else {
        for( int i = wf ; i <= s ; ++ i )
            ( re += 1ll * J[i] % P * dp[u][i] % P * C( i - 1 , wf - 1 ) % P ) %= P;
    }
    res = 1ll * res * re % P;

分当前是否在处理 $1$ 讨论。

如果在处理根，就不需要管父亲的边了，直接给 $dp[u][i]$ 乘上 $i!$ 就完事了，因为之前已经除过每个相同颜色的数量的阶乘了。

如果当前处理的不是根，我们考虑它的父亲的出现次数是到父亲的边权一半 + 1，所以至少需要保留 wf 个（这里的 wf 就是到父亲边权的一半），然后由于开头结尾必须是父亲，所以系数是 $i - 1\choose wf - 1$ 这个东西。

然后由于所有 $S_u$ 独立，方案数量就是乘起来。

最终代码：

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 5006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
//#define P 1000000007
typedef long long ll;
int n , P;
vector<pii> G[MAXN];
int dp[MAXN][MAXN] , siz[MAXN];

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = 1ll * ret * x % P;
        x = 1ll * x * x % P , a >>= 1;
    }
    return ret;
}

int J[MAXN] , iJ[MAXN];
int C( int a , int b ) {
    return 1ll * J[a] * iJ[b] % P * iJ[a - b] % P;
}

int res = 1;
int td[MAXN];
void dfs( int u , int fa , int wf ) {
    int s;
    if( u != 1 ) dp[u][1] = 1 , s = 1; // currently only 0 in S_u
    else dp[u][0] = 1 , s = 0;
    for( auto& t : G[u] ) if( t.fi != fa ) {
        int v = t.fi;
        dfs( v , u , t.se / 2 );
        for( int i = 0 ; i <= s ; ++ i )
            for( int j = 1 ; j <= t.se / 2 ; ++ j ) { // j : the rest after merging
                ( td[i + j] += 1ll * dp[u][i] * C( t.se / 2 - 1 , t.se / 2 - j ) % P * iJ[j] % P * ( ( t.se / 2 - j & 1 ) ? P - 1 : 1 ) % P ) %= P;
            }
        for( int i = 0 ; i <= s + t.se ; ++ i ) dp[u][i] = td[i] , td[i] = 0;
        s += t.se / 2;
    }
    int re = 0;
    if( u == 1 ) {
        for( int i = 0 ; i <= s ; ++ i ) ( re += 1ll * J[i] % P * dp[u][i] % P ) %= P;
    } else {
        for( int i = wf ; i <= s ; ++ i )
            ( re += 1ll * J[i] % P * dp[u][i] % P * C( i - 1 , wf - 1 ) % P ) %= P;
    }
    res = 1ll * res * re % P;
}
void solve() {
    cin >> n >> P;
    J[0] = iJ[0] = 1;
    rep( i , 1 , n ) J[i] = 1ll * J[i - 1] * i % P , iJ[i] = Pow( J[i] , P - 2 );
    int u , v , w;
    rep( i , 1 , n - 1 ) scanf("%d%d%d",&u,&v,&w) , G[u].eb( mp( v , w ) ) , G[v].eb( mp( u , w ) );
    dfs( 1 , 1 , 0 );
    cout << 1ll * res * n % P << endl;
}
signed main() {
//    freopen("2.in","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}