Submission #1160070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160070		KluydQ	Star Trek (CEOI20_startrek)	C++20	100 / 100	55 ms	21008 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], sumw[N], suml[N];
vector <int> g[N];
int E = 0, L = 0;

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 )
{
	for( auto to : g[v] )
	{
		if( to == p ) continue;
		set_critical( to, v );
		if( win[to] ) sumw[v] += c[to];
		else suml[v] += c[to];
	}
	if( win[v] )
	{
		if( num[v] >= 2 ) c[v] = 0;
		else c[v] = suml[v];
	}
	else c[v] = sumw[v] + 1;
}
void zam( int v, int u )
{
	if( win[u] ) sumw[v] -= c[u];
	else suml[v] -= c[u];
	num[v] -= !win[u];
	win[v] = num[v] >= 1;
	
	if( win[v] )
	{
		if( num[v] >= 2 ) c[v] = 0;
		else c[v] = suml[v];
	}
	else c[v] = sumw[v] + 1;
	
	if( win[v] ) sumw[u] += c[v];
	else suml[u] += c[v];
	num[u] += !win[v];
	win[u] = num[u] >= 1;
	
	if( win[u] )
	{
		if( num[u] >= 2 ) c[u] = 0;
		else c[u] = suml[u];
	}
	else c[u] = sumw[u] + 1;
}
void calc( int v, int p = 0 )
{
	E = ( E + ( win[v] ? 1 : -1 ) * c[v] + mod ) % mod;
	L += !win[v];
	
	for( int to : g[v] ) 
	{
		if( to != p )
		{
			zam( v, to );
			calc( to, v );
			zam( to, v );
		}
	}
}
struct mt
{
	int a[3][3];
	
	mt()
	{
		FOR( i, 1, 2, 1 )
		{
			FOR( j, 1, 2, 1 ) a[i][j] = 0;
		}
	}
	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 );
	
	calc(1);
	
	// L[d] = L[d - 1] * E + N ^ 2d * |L|;
	
	st.a[1][1] = L, st.a[1][2] = n * n % mod * L % mod;
	mul.a[1][1] = E, mul.a[2][1] = 1, mul.a[2][2] = n * n % mod;
	int cur = binmt( k - 1 );
	
	if( !win[1] ) cout << cur * c[1] % mod;
	else cout << ( binpow( n, 2 * k ) - cur * c[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: 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