Submission #1160043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160043		KluydQ	Star Trek (CEOI20_startrek)	C++20	0 / 100	5 ms	7496 KiB

startrek

#include <bits/stdc++.h>
//#include "arithmetics.h"

#define respagold ios_base::sync_with_stdio(0), cin.tie(0);
#define int long long
#define ll long long
#define int2 __int128_t
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define pii pair <int, int>
#define mkp make_pair
 
using namespace std;

const int N = 3e5 + 123;
const int inf = 1e18;
const int mod = 1e9 + 7;
const double eps = 1e-13;

int a[N], b[N], n, m, k, z, x, y, w;
int win[N], num[N], c[N];
vector <int> g[N];
int ans[N], erfg[N];

mt19937 rng( chrono::steady_clock::now().time_since_epoch().count());

int binpow( int a, int b )
{
	if( !b ) return 1;
	if( b % 2 ) return binpow( a, b - 1 ) * a % mod;
	int res = binpow( a, b / 2 ); return res * res % mod;
}
void set_state( int v, int p )
{
	for( auto to : g[v] )
	{
		if( to == p ) continue;
		set_state( to, v );
		win[v] |= !win[to];
		num[v] += !win[to];
	}
}
void set_critical( int v, int p )
{
	c[v] = !win[v];
	
	for( auto to : g[v] )
	{
		if( to == p ) continue;
		set_critical( to, v );
		if( win[to] != win[v] ) c[v] += c[to];
	}
	if( win[v] && num[v] >= 2 ) c[v] = 0;
}

void sdg( int v , int p)
{
	c[v] = !win[v];
	
	for( auto to : g[v] )
	{
		if( to == p ) continue;
		if( win[to] != win[v] ) c[v] += c[to];
	}
	if( win[v] && num[v] >= 2 ) c[v] = 0;
}

void zam( int v, int u )
{
	c[u] = c[v];
	int cnt = 0;
	
	for( int to : g[v] ) 
	{
		if( to != u && !win[to] ) cnt ++;
	}
	if( cnt >= 1 ) win[v] = 1;
	else win[v] = 0;
	
	cnt = 0;
	
	for( int to : g[v] )
	{
		if( !win[to] ) cnt ++;
	}
	if(cnt >= 1) win[v] = 1;
	else win[v] = 0;
	
	sdg( v, u );
	sdg( u, u );
}

void calc( int v , int p = 0 )
{
	for(int to : g[v]) 
	{
		if( to != p )
		{
			zam( v, to );
			calc( to, v );
		}
	}
	ans[v] = c[v];
	erfg[v] = win[v];
	zam( v, p );
}
struct mt
{
	int a[3][3];
	
	mt()
	{
		FOR( i, 1, 2, 1 )
		{
			FOR( j, 1, 2, 1 ) a[i][j] = inf;
		}
	}
	mt operator *( mt b )
	{
		mt c = mt();
		
		FOR( i, 1, 2, 1 )
		{
			FOR( j, 1, 2, 1 )
			{
				FOR( k, 1, 2, 1 ) c.a[i][j] = ( c.a[i][j] + a[i][k] * b.a[k][j] ) % mod;
			}
		}
		return c;
	}
};
mt st, mul;

int binmt( int x )
{
	mt res = st, pw = mul;
	
	while( x )
	{
		if( x & 1ll ) res = res * pw;
		pw = pw * pw; x >>= 1ll;
	}
	return res.a[1][1];
}
void solve()
{
	cin >> n >> k;
	
	FOR( i, 1, n - 1, 1 )
	{
		cin >> x >> y;
		g[x].pb(y), g[y].pb(x);
	}
	set_state( 1, 0 );
	set_critical( 1, 0 );
	
	ans[1] = c[1];
	calc(1);
	
	int E = 0, L = 0;
	FOR( i, 1, n, 1 ) E = ( E + ( erfg[i] ? 1 : -1 ) * c[i] + mod ) % mod, L += !erfg[i];
	
	// L[d] = L[d - 1] * E + N ^ 2d * |L|;
	
	st.a[1][1] = L, st.a[2][2] = L;
	mul.a[1][1] = E, mul.a[2][1] = n * n % mod, mul.a[2][2] = n * n % mod;
	int cur = binmt( k - 1 );
	
	if( !erfg[1] ) cout << cur * ans[1] % mod;
	else cout << ( binpow( n, 2 * k ) - cur * ans[1] % mod + mod ) % mod;
}
signed main()
{
//	freopen("connect.in", "r", stdin);
//	freopen("connect.out", "w", stdout);
	    
    respagold
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
// solved by KluydQ

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