「CEOI2020」星际迷航

首先是最简单的判断是否必胜的$dp$转移$\displaystyle dp_u=\bigcup_{v\in son_u} \text{not } dp_{v}$

考虑第$i+1$层对于第$i$层的贡献，实际上只和$i+1$层有多少个点$dp$值为0/1有关

下面称$dp$值为0/1的点为 败/胜 点

考虑对于确定第$i$层的根为某一节点$root$之后

在某一个点下面接一个胜点，或者在一个胜点下面接一个点，对于胜败情况没有影响

在一个败点下面接一个败点，可能会导致一段连续祖先段的胜败翻转

考虑对于每个$u$作为根求出：

1.没有接上下一层时的胜败情况 ： $dp_u$

2.有多少个节点接上一个败点之后，会导致根的胜败情况翻转：$R_u$

这是一个换根$dp$问题

具体来说，$R_u$的值，根据子节点中败点的个数可以得到转移：

1.没有败点，那么就是所有子节点$R$之和+自己

2.恰好有一个败点，那么就是败点的$R$

对此，每个点维护子节点中败点的个数，然后换根$dp$即可

求出每个$root$的1，2后，可以用一个矩阵维护每层的转移，就不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
    int s=0;
    while(!isdigit(IO=getchar()));
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return s;
}

const int N=1e5+10,INF=1e9+10,P=1e9+7;

int n;
ll m;
struct Mat{
    int a[2][2];
    void clear(){ memset(a,0,sizeof a); }
    Mat operator * (const Mat x) const {
        Mat res; res.clear();
        rep(i,0,1) rep(j,0,1) rep(k,0,1) res.a[i][k]=(res.a[i][k]+1ll*a[i][j]*x.a[j][k])%P;
        return res;
    }
} Res,X;

int F[N],FC[N],FR[N],son[N][2],SR[N];
// F子树胜败，FC子节点败点个数，FR子树翻转点个数，son存储两个儿子中的败点，SR存储儿子中的FR之和
int G[N],GC[N],GR[N];
// F,GC,GR是子树外的
int dp[N],R[N],fa[N];
// dp,R即上文所述

vector <int> E[N];
void dfs1(int u,int f) {
    // 子树处理
    fa[u]=f;
    for(int v:E[u]) if(v!=f) {
        dfs1(v,u);
        FC[u]+=!F[v];
        if(!F[v]) {
            if(!son[u][0]) son[u][0]=v;
            else son[u][1]=v;
        }
        SR[u]+=FR[v];
    }
    F[u]=FC[u]>0;
    FR[u]=!F[u];
    if(FC[u]<=1) for(int v:E[u]) if(v!=f && F[u]!=F[v]) FR[u]+=FR[v];
}

//换根dp
void dfs2(int u,int f) {
    if(f) GC[u]=G[u]=!G[f],GR[u]=GR[f]+!G[u];
    else GC[u]=G[u]=0,GR[u]=1;
    dp[u]=F[u]|G[u];
    if(!dp[u]) R[u]=FR[u]+GR[u]-1;
    else if(FC[u]+G[u]==1) {
        if(G[u]) R[u]=GR[u];
        else R[u]=FR[u];
    }
    for(int v:E[u]) if(v!=f) {
        GC[u]=FC[u]-!F[v]+(f?!G[f]:0);
        G[u]=GC[u]>0;
        GR[u]=0;
        if(!G[u]) GR[u]=GR[f]+SR[u]-FR[v]+1;
        else if(GC[u]==1) {
            if(son[u][0] && son[u][0]!=v) GR[u]=FR[son[u][0]];
            else if(son[u][1] && son[u][1]!=v) GR[u]=FR[son[u][1]];
            else GR[u]=GR[f];
        }
        dfs2(v,u);
    }
}

int cnt[2];
int main(){
    n=rd(),scanf("%lld",&m);
    rep(i,2,n) {
        int u=rd(),v=rd();
        E[u].pb(v),E[v].pb(u);
    }
    dfs1(1,0),dfs2(1,0);
    // 矩阵处理
    rep(i,1,n) {
        cnt[dp[i]]++;
        X.a[1][dp[i]]=(X.a[1][dp[i]]+n)%P;
        X.a[0][!dp[i]]=(X.a[0][!dp[i]]+R[i])%P;
        X.a[0][dp[i]]=(X.a[0][dp[i]]+n-R[i])%P;
    }
    m--,Res.a[0][0]=Res.a[1][1]=1;
    while(m) {
        if(m&1) Res=Res*X;
        X=X*X;
        m>>=1;
    }
    int x=(1ll*Res.a[0][0]*cnt[0]+1ll*Res.a[1][0]*cnt[1])%P;
    int y=(1ll*Res.a[0][1]*cnt[0]+1ll*Res.a[1][1]*cnt[1])%P;
    // 得到第一层败/胜 的个数，与第0层合并
    int ans=0;
    if(!dp[1]) ans=1ll*x*R[1]%P;
    else ans=(1ll*x*(n-R[1])+1ll*n*y)%P;
    printf("%d\n",ans);
}