Submission #343166

#	Time	Username	Problem	Language	Result	Execution time	Memory
343166		sealnot123	Star Trek (CEOI20_startrek)	C++14	100 / 100	150 ms	18796 KiB

startrek

/*
	Author: AquaBlaze
	Time: 2021-01-03 18:10:22
	Generated by powerful Codeforces Tool :^)
 	You can download the binary file in here https://github.com/xalanq/cf-tool (Windows, macOS, Linux)	
    Keqing best girl :)
    Nephren will always be in my heart
*/
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())
#define pc(x) putchar(x)
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long i64;
typedef tuple<int,int,int> iii;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 100005;
const int mod = 1000000007;

int add(int a, int b){ return ((a+=b)>=mod)?a-mod:a; }
void adding(int &a, int b){ a = add(a, b); }
int mul(int a, int b){ return a*1ll*b%mod; }

pii operator + (const pii& A, const pii& B){
    return pii(add(A.x,B.x), add(A.y,B.y));
}
pii operator - (const pii& A, const pii& B){
    return pii(add(A.x,mod-B.x), add(A.y,mod-B.y));
}
inline pii& operator += (pii& A, const pii& B){
    A = A+B;
    return A;
}
inline pii& operator -= (pii& A, const pii& B){
    A = A-B;
    return A;
}

vi g[N];
pii dp[N][2], final_dp[N][2], sum[N][2], lose[N][2];
int result[N], final_res[N];

void adjust(int u){
    if(result[u]) dp[u][1]+=pii(1,1);
    else{
        dp[u][1]+=pii(0,1);
        dp[u][0]+=pii(1,0);
    }
}

void dejust(int u){
    if(result[u]) dp[u][1]-=pii(1,1);
    else{
        dp[u][1]-=pii(0,1);
        dp[u][0]-=pii(1,0);
    }
}

void add_node(int u, int v){
    dejust(u);
    if(result[u]==0){
        if(!result[v]){
            dp[u][1] = sum[u][0]+sum[u][1]+dp[v][0];
            dp[u][0] = dp[v][1];
        }else{
            dp[u][1] += dp[v][0];
            dp[u][0] += dp[v][1];
        }
    }else if(result[u]==1){
        if(!result[v]){
            dp[u][0] -= lose[u][1];
            dp[u][1] += lose[u][1]+dp[v][0]+dp[v][1];
        }else{
            dp[u][1] += dp[v][0]+dp[v][1];
        }
    }else{
        dp[u][1] += dp[v][0]+dp[v][1];
    }

    if(!result[v]){
        FOR(i,0,1) lose[u][i]+=dp[v][i];
    }
    result[u] += !result[v];
    adjust(u);
    FOR(i,0,1) sum[u][i]+=dp[v][i];
}

void sub_node(int u, int v){
    dejust(u);
    if(result[u]==0){
        if(!result[v]){
            assert(0);
        }else{
            dp[u][1] -= dp[v][0];
            dp[u][0] -= dp[v][1];
        }
    }else if(result[u]==1){
        if(!result[v]){
            dp[u][0] = sum[u][1]-dp[v][1];
            dp[u][1] = sum[u][0]-dp[v][0];
        }else{
            dp[u][1] -= dp[v][0]+dp[v][1];
        }
    }else if(result[u]==2){
        if(!result[v]){
            dp[u][1] -= lose[u][0]+lose[u][1];
            dp[u][1] += lose[u][0]-dp[v][0];
            dp[u][0] += lose[u][1]-dp[v][1];
        }else{
            dp[u][1] -= dp[v][0]+dp[v][1];
        }
    }else{
        dp[u][1] -= dp[v][0]+dp[v][1];
    }

    if(!result[v]){
        FOR(i,0,1) lose[u][i]-=dp[v][i];
    }
    result[u] -= !result[v];
    adjust(u);
    FOR(i,0,1) sum[u][i]-=dp[v][i];
}

void dfs(int u, int p){
    for(int &e : g[u]){
        if(e == p){
            swap(e, g[u].back());
            g[u].pop_back();
            break;
        }
    }
    for(const int &e : g[u]){
        dfs(e, u);
    }
    adjust(u);
    for(const int &e : g[u]){
        add_node(u, e);
    }
}

void tour(int u){
    final_res[u] = !(!result[u]);
    FOR(i, 0, 1) final_dp[u][i]=dp[u][i];
    for(const int &e : g[u]){
        sub_node(u, e);
        add_node(e, u);
        tour(e);
        sub_node(e, u);
        add_node(u, e);
    }
}

vvi pw[60];

void solve(){
    int n;
    i64 d;
    cin >> n >> d;
    FOR(i, 2, n){
        int a, b;
        cin >> a >> b;
        g[a].eb(b);
        g[b].eb(a);
    }
    dfs(1, -1);
    tour(1);

    assert(dp[1][0]==final_dp[1][0]);
    assert(dp[1][1]==final_dp[1][1]);

    pw[0].resize(2,vi(2, 0));
    FOR(i, 1, n){
        FOR(j, 0, 1){
            adding(pw[0][j^1][0], final_dp[i][j].x);
            adding(pw[0][j^1][1], final_dp[i][j].y);
        }
    }
    FOR(t, 1, 59){
        pw[t].resize(2, vi(2, 0));
        FOR(i, 0, 1){
            FOR(j, 0, 1){
                FOR(k, 0, 1){
                    adding(pw[t][i][j], mul(pw[t-1][i][k],pw[t-1][k][j]));
                }
            }
        }
    }
    vi res(2,0);
    FOR(i, 1, n) res[1-final_res[i]]++;
    --d;
    FOR(t, 0, 59){
        if(d&(1ll<<t)){
            vi tmp(2,0);
            FOR(i, 0, 1){
                FOR(j, 0, 1){
                    adding(tmp[i], mul(res[j],pw[t][i][j]));
                }
            }
            res = tmp;
        }
    }
    pii p = dp[1][1];
    int ans = add(mul(p.x,res[0]),mul(p.y,res[1]));
    printf("%d",ans);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 15 / 15