//雪花飄飄北風嘯嘯
//天地一片蒼茫
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct custom_hash {
typedef unsigned long long ull;
const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
static ull splitmix64(ull x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(ll x) const {
return splitmix64(x + FIXED_RANDOM);
}
size_t operator()(const pair<int,int> &i)const{
return splitmix64((((ll)i.first)^(((ll)i.second)<<32))+FIXED_RANDOM);
}
};
const int MOD=1000000007;
vector<vector<ll> > mul(vector<vector<ll> > i, vector<vector<ll> > j,int m){
vector<vector<ll> > res;
for (int x=0;x<i.size();x++){
res.push_back(vector<ll>());
for (int y=0;y<i.size();y++){
res[x].push_back(0);
for (int z=0;z<i.size();z++){
res[x][y]=(res[x][y]+i[x][z]*j[z][y])%m;
}
}
}
return res;
}
vector<vector<ll> > mexp(vector<vector<ll> > mat,long long p,int m){
if (p==1) return mat;
vector<vector<ll> > res=mexp(mat,p>>1,m);
res=mul(res,res,m);
if (p&1) res=mul(res,mat,m);
return res;
}
ll qexp(ll b,ll p,int m){
ll res=1;
while (p){
if (p&1) res=res*b%m;
b=b*b%m;
p>>=1;
}
return res;
}
ll fix(ll i){
i%=MOD;
if (i<0) i+=MOD;
return i;
}
ll n,k;
vector<int> al[100005];
struct pi{
ll a=0,b=0;
};
pi add(pi i,pi j){
pi res;
res.a=(i.a+j.a)%MOD;
res.b=(i.b+j.b)%MOD;
return res;
}
pi mul(pi i,pi j){
pi res;
res.a=(i.a*j.b)%MOD;
res.b=fix((i.a+i.b)*(j.a+j.b)-res.a);
return res;
}
struct dat{
pi norm;
pi extra;
};
struct mat{ //operation of tree
int v[4][4];
mat(int i){
memset(v,0,sizeof(v));
rep(x,0,4) v[x][x]=i;
}
mat(int a,int b,int c,int d){
memset(v,0,sizeof(v));
v[0][0]=b;
v[1][0]=a;
v[1][1]=(a+b)%MOD;
v[2][2]=b;
v[3][2]=a;
v[3][3]=(a+b)%MOD;
v[2][0]=d;
v[3][0]=c;
v[3][1]=(c+d)%MOD;
}
};
mat mul(mat &i, mat &j){
mat res=mat(0);
rep(x,0,4) rep(y,0,4) rep(z,0,4)
res.v[x][y]=(res.v[x][y]+i.v[x][z]*j.v[z][y])%MOD;
return res;
}
pi pp;
unordered_map<ii,dat,custom_hash> memo;
int pa[100005];
vector<int> adj[100005];
vector<mat> fw[100005],bw[100005];
dat dfs(int i,int p){
if (memo.count(ii(i,p))) return memo[ii(i,p)];
mat matt=mat(1);
if (pa[i]==0){
pa[i]=p;
vector<mat> v;
for (auto &it:al[i]){
if (it==p) continue;
adj[i].push_back(it);
auto res=dfs(it,i);
v.push_back(mat(res.norm.a,res.norm.b,res.extra.a,res.extra.b));
}
if (sz(v)==1) fw[i].push_back(v[0]),bw[i].push_back(v[0]);
else if (sz(v)>1){
fw[i].push_back(v[0]);
rep(x,1,sz(v)) fw[i].push_back(mul(fw[i].back(),v[x]));
reverse(all(v));
bw[i].push_back(v[0]);
rep(x,1,sz(v)) bw[i].push_back(mul(bw[i].back(),v[x]));
reverse(all(bw[i]));
}
if (!v.empty()) matt=fw[i].back();
}
else{
if (pa[i]!=-1){
auto res=dfs(pa[i],i);
auto temp=mat(res.norm.a,res.norm.b,res.extra.a,res.extra.b);
matt=mul(matt,temp);
}
if (!adj[i].empty()){
if (p==-1){
matt=mul(matt,fw[i].back());
}
else{
int idx=distance(adj[i].begin(),lower_bound(all(adj[i]),p));
if (idx!=0) matt=mul(matt,fw[i][idx-1]);
if (idx!=sz(adj[i])-1) matt=mul(matt,bw[i][idx+1]);
}
}
}
dat res;
res.norm.a=matt.v[0][0],res.norm.b=matt.v[1][0];
res.extra.a=matt.v[2][0],res.extra.b=matt.v[3][0];
res.extra=add(res.extra,mul(res.norm,pp));
return memo[ii(i,p)]=res;
}
dat get(int i,int j){
pp.a=i,pp.b=j;
memo.clear();
rep(x,0,100005){
pa[x]=0;
adj[x].clear();
fw[x].clear();
bw[x].clear();
}
dat temp;
rep(x,1,n+1){
auto res=dfs(x,-1);
temp.norm=add(temp.norm,res.norm);
temp.extra=add(temp.extra,res.extra);
}
return temp;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
memo.reserve(4096);
memo.max_load_factor(0.25);
cin>>n>>k;
ll a,b;
rep(x,1,n){
cin>>a>>b;
al[a].push_back(b);
al[b].push_back(a);
}
rep(x,1,n+1) sort(all(al[x]));
vector<vector<ll> > mat={{0,0},{0,0}};
dat temp;
temp=get(1,0);
mat[0][0]=temp.extra.a%MOD,mat[1][0]=temp.extra.b%MOD;
temp=get(0,1);
mat[0][1]=temp.extra.a%MOD,mat[1][1]=temp.extra.b%MOD;
//cout<<mat[0][0]<<" "<<mat[0][1]<<endl;
//cout<<mat[1][0]<<" "<<mat[1][1]<<endl;
if (k==1) mat={{1,0},{0,1}};
else mat=mexp(mat,k-1,MOD);
temp=get(0,0);
a=temp.norm.a%MOD,b=temp.norm.b%MOD;
//cout<<a<<" "<<b<<endl;
get((mat[0][0]*a+mat[0][1]*b)%MOD,(mat[1][0]*a+mat[1][1]*b)%MOD);
cout<<dfs(1,-1).extra.b<<endl;
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/gthr.h:148,
from /usr/include/c++/9/ext/atomicity.h:35,
from /usr/include/c++/9/bits/ios_base.h:39,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from startrek.cpp:8:
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:71:3: error: option("tune=") was already specified
71 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:71:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:72:3: error: option("tune=") was already specified
72 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:72:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:73:3: error: option("tune=") was already specified
73 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:73:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:74:3: error: option("tune=") was already specified
74 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:74:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:75:3: error: option("tune=") was already specified
75 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:75:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:89:4: error: option("tune=") was already specified
89 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/9/shared_mutex:89:4: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:99:4: error: option("tune=") was already specified
99 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/9/shared_mutex:99:4: error: option("tune=") was already specified
startrek.cpp: In function 'std::vector<std::vector<long long int> > mul(std::vector<std::vector<long long int> >, std::vector<std::vector<long long int> >, int)':
startrek.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int x=0;x<i.size();x++){
| ~^~~~~~~~~
startrek.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int y=0;y<i.size();y++){
| ~^~~~~~~~~
startrek.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int z=0;z<i.size();z++){
| ~^~~~~~~~~
