Submission #459170

#	Time	Username	Problem	Language	Result	Execution time	Memory
459170		AmShZ	Star Trek (CEOI20_startrek)	C++11	100 / 100	116 ms	18464 KiB

startrek

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 1e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int n, dp[2][xn], sz[2][xn], par[xn], ans;
bool f[2][xn];
ll D;
vector <int> adj[xn];

void DFS(int v, int p = - 1){
	sz[0][v] = 1;
	int ted = 0;
	for (int u : adj[v]){
		if (u == p)
			continue;
		par[u] = v;
		DFS(u, v);
		f[0][v] |= !(f[0][u]);
		sz[0][v] += sz[0][u];
		ted += !f[0][u];
	}
	dp[0][v] = sz[0][v];
	for (int u : adj[v])
		if (u != p && ted == !f[0][u])
			dp[0][v] -= dp[0][u];
}
void DFS2(int v, int p = - 1){
	int ted = !f[1][v];
	for (int u : adj[v])
		if (u != p)
			ted += !f[0][u], sz[1][v] += sz[0][u];
	++ sz[1][v];
	int sum0 = 0, sum1 = 0;
	for (int u : adj[v]){
		if (u == p)
			continue;
		sz[1][u] = sz[1][v] - sz[0][u];
		dp[1][u] = sz[1][u];
		dp[1][u] = n - sz[0][u];
		f[1][u] = (0 < ted - !f[0][u]);
		if (f[0][u])
			sum1 += dp[0][u];
		else
			sum0 += dp[0][u];
	}
	if (f[1][v])
		sum1 += dp[1][v];
	else
		sum0 += dp[1][v];
	for (int u : adj[v]){
		if (u == p)
			continue;
		if (f[0][u])
			sum1 -= dp[0][u];
		else
			sum0 -= dp[0][u];
		if (ted - !f[0][u] == 0)
			dp[1][u] -= sum1;
		else if (ted - !f[0][u] == 1)
			dp[1][u] -= sum0;
		if (f[0][u])
			sum1 += dp[0][u];
		else
			sum0 += dp[0][u];
		DFS2(u, v);
	}
}

struct matrix{
    int a[2][2];
    matrix operator * (const matrix &t){
        matrix r;
        for (int i = 0; i < 2; ++ i)
        	for (int j = 0; j < 2; ++ j)
        		r.a[i][j] = 0;
        for (int i = 0; i < 2; ++ i)
        	for (int j = 0; j < 2; ++ j)
        		for (int k = 0; k < 2; ++ k)
        			r.a[i][k] = (r.a[i][k] + 1ll * a[i][j] * t.a[!j][k] % mod) % mod;
        return r;
    }
};
matrix Pow(matrix a, ll b){
    matrix res = a;
    if (b < 0)
    	return res;
    for (; b; b = b >> 1){
        if (b & 1)
            res = res * a;
        a = a * a;
    }
    return res;
}

int main(){
	fast_io;

	cin >> n >> D;
	for (int i = 0; i < n - 1; ++ i){
		int v, u;
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	DFS(1);
	f[1][1] = 1;
	DFS2(1);
	matrix M;
	for (int i = 0; i < 2; ++ i)
		for (int j = 0; j < 2; ++ j)
			M.a[i][j] = 0;
	pii last;
	for (int v = 1; v <= n; ++ v){
		bool fl = !f[1][v];
		int ted = !f[1][v];
		for (int u : adj[v]){
			if (u == par[v])
				continue;
			fl |= !f[0][u];
			ted += !f[0][u];
		}
		int val = n;
		if (ted == !f[1][v])
			val -= dp[1][v];
		for (int u : adj[v])
			if (u != par[v] && ted == !f[0][u])
				val -= dp[0][u];
		M.a[1][1] = (M.a[1][1] + val) % mod;
		M.a[0][1] = (M.a[0][1] + n - val) % mod;
		if (fl)
			M.a[1][0] = (M.a[1][0] + n) % mod;
		else
			M.a[0][0] = (M.a[0][0] + n) % mod;
		if (v == 1)
			last = {fl, val};
	}
	M = Pow(M, D - 1);
	if (last.A)
		ans = (ans + 1ll * n * M.a[1][0] % mod) % mod;
	ans = (ans + 1ll * last.B * M.a[0][0] % mod) % mod;
	ans = 1ll * ans * power(n, mod - 2, mod) % mod;
	cout << ans << endl;

	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