結果
問題 | No.1075 木の上の山 |
ユーザー |
|
提出日時 | 2020-06-05 22:32:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 11,207 bytes |
コンパイル時間 | 4,564 ms |
コンパイル使用メモリ | 239,632 KB |
最終ジャッジ日時 | 2025-01-10 22:44:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
コンパイルメッセージ
main.cpp:273:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type] 273 | main(){ | ^~~~ main.cpp: In function ‘void scan(char*)’: main.cpp:52:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 52 | void scan(char a[]){ scanf("%s", a); } | ~~~~~^~~~~~~~~
ソースコード
#pragma region Macros#pragma GCC optimize("O3")#include <bits/stdc++.h>#define ll long long#define ld long double#define rep2(i,a,b) for(ll i=a;i<=b;++i)#define rep(i,n) for(ll i=0;i<n;++i)#define rep3(i,a,b) for(ll i=a;i>=b;--i)#define pii pair<int,int>#define pll pair<ll,ll>#define pb push_back#define eb emplace_back#define vi vector<int>#define vec vector<int>#define vll vector<ll>#define vpi vector<pii>#define vpll vector<pll>#define overload2(_1,_2,name,...) name#define vv(a,b) vector<vector<int>>(a,vector<int>(b))#define vv2(a,b,c) vector<vector<int>>(a,vector<int>(b,c))#define vvl(a,b) vector<vector<ll>>(a,vector<ll>(b))#define vvl2(a,b,c) vector<vector<ll>>(a,vector<ll>(b,c))#define vvv(a,b,c) vector<vv(b,c)>(a)#define vvv2(a,b,c,d) vector<vv(b,c,d)>(a)#define vvvl(a,b,c) vector<vvl(b,c)>(a)#define vvvl2(a,b,c,d) vector<vvl(b,c,d)>(a)#define fi first#define se second#define all(c) begin(c),end(c)#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);#define lb(c,x) distance((c).begin(),lower_bound(all(c),(x)))#define ub(c,x) distance((c).begin(),upper_bound(all(c),(x)))using namespace std;template<class T> using pq = priority_queue<T>;template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;#define Size(c) (int)(c).size()#define INT(...) int __VA_ARGS__;IN(__VA_ARGS__)#define LL(...) ll __VA_ARGS__;IN(__VA_ARGS__)#define ULL(...) ull __VA_ARGS__;IN(__VA_ARGS__)#define STR(...) string __VA_ARGS__;IN(__VA_ARGS__)#define CHR(...) char __VA_ARGS__;IN(__VA_ARGS__)#define DBL(...) double __VA_ARGS__;IN(__VA_ARGS__)#define LD(...) ld __VA_ARGS__;IN(__VA_ARGS__)#define VEC(type,name,size) vector<type> name(size);IN(name)#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));IN(name)int scan(){ return getchar(); }void scan(int& a){ cin>>a; }void scan(long long& a){ cin>>a; }void scan(char &a){cin>>a;}void scan(double &a){ cin>>a; }void scan(long double& a){ cin>>a; }void scan(char a[]){ scanf("%s", a); }void scan(string& a){ cin >> a; }template<class T> void scan(vector<T>&);template<class T, size_t size> void scan(array<T, size>&);template<class T, class L> void scan(pair<T, L>&);template<class T, size_t size> void scan(T(&)[size]);template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }template<class T> void scan(deque<T>& a){ for(auto& i : a) scan(i); }template<class T, size_t size> void scan(array<T, size>& a){ for(auto& i : a) scan(i); }template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }template<class T, size_t size> void scan(T (&a)[size]){ for(auto& i : a) scan(i); }template<class T> void scan(T& a){ cin >> a; }void IN(){}template <class Head, class... Tail> void IN(Head& head, Tail&... tail){ scan(head); IN(tail...); }string stin() {string s;cin>>s;return s;}template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}vi iota(int n){vi a(n);iota(all(a),0);return a;}template<class T> void UNIQUE(vector<T> &x){sort(all(x));x.erase(unique(all(x)),x.end());}int in() {int x;cin>>x;return x;}ll lin() {unsigned long long x;cin>>x;return x;}void print(){putchar(' ');}void print(bool a){cout<<a;}void print(int a){cout<<a;}void print(long long a){cout<<a;}void print(char a){cout<<a;}void print(string &a){cout<<a;}void print(double a){cout<<a;}template<class T> void print(const vector<T>&);template<class T, size_t size> void print(const array<T, size>&);template<class T, class L> void print(const pair<T, L>& p);template<class T, size_t size> void print(const T (&)[size]);template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i);} cout<<endl;}template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i);} }template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }template<class T, class L> void print(const pair<T, L>& p){ cout<<'(';print(p.first); cout<<","; print(p.second);cout<<')'; }template<class T> void print(set<T> &x){for(auto e:x)print(e),cout<<" ";cout<<endl;}template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ cout<<" "; print(*i); } }template<class T> void print(const T& a){ cout << a; }int out(){ putchar('\n'); return 0; }template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }ll gcd(ll a, ll b){ a = abs(a),b = abs(b);while(b){ ll c = b; b = a % b; a = c; } return a; }ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }vector<pll> factor(ll x){ vector<pll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }vector<int> divisor(int x){ vector<int> ans; for(int i=1;i*i<=x;i++)if(x%i==0){ans.pb(i);if(i*i!=x)ans.pb(x/i);} return ans;}int popcount(ll x){return __builtin_popcountll(x);}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int rnd(int n){return uniform_int_distribution<int>(0, n-1)(rng);}#define endl '\n'#ifdef _LOCAL#undef endl#define debug(x) cout<<#x<<": ";print(x);cout<<endl;void err(){}template<class T> void err(const T& t){ print(t); cout<<" ";}template<class Head, class... Tail> void err(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); }#else#define debug(x)template<class... T> void err(const T&...){}#endifstruct Setup_io{ Setup_io(){ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);}}setup_io;#pragma endregion// _______ここから編集!_______________template< typename T >struct edge{int from, to,id;T cost;edge(int to,T cost) : from(-1), to(to), cost(cost){}edge(int from,int to,T cost) : from(from), to(to), cost(cost){}edge(int from,int to,T cost,int id):from(from),to(to),cost(cost){}edge &operator=(const int &x) {to = x;return *this;}operator int() const{ return to;}};template< typename T >using Edges = vector< edge< T > >;template< typename T >using WeightedTree = vector< Edges<T>>;using tree = vector< vector<int> >;tree make(int n,int offset = 1){tree res(n);for(int i = 0;i < n-1; i++){int a,b; cin >> a >> b;a -= offset,b -= offset;res[a].emplace_back(b);res[b].emplace_back(a);}return res;}template< typename T >WeightedTree<T> make2(int n, int offset = 1){WeightedTree<T> res(n);for(int i = 0;i < n-1 ; i++){int a,b ; cin >> a >> b;a -= offset, b -= offset;T c; cin >> c;res[a].emplace_back(b,c);res[b].emplace_back(a,c);}return res;}const ll MOD=1e9+7;const int N=1100000;template <ll Modulus> class modint {using u64 = ll;public:u64 a;constexpr modint(const u64 x = 0) noexcept : a(((x % Modulus) + Modulus)%Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if (a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if (a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = Modulus - 2;while (exp) {if (exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}};#define mint modint<MOD>mint inv[N],comb[N],prd[N],invprd[N];void calc_inv(){inv[1]=1;rep2(i,2,N-1){inv[i]=inv[MOD%i]*(-MOD/i);}return;}void calc_product(){prd[0]=prd[1]=1;invprd[0]=invprd[1]=1;rep2(i,2,N-1){prd[i]=prd[i-1]*i;invprd[i]=inv[i]*invprd[i-1];}return ;}mint cmb(int a,int b){if(a<b)return 0;if(a<0||b<0)return 0;return {prd[a]*invprd[b]*invprd[a-b]};}mint modpow(mint x,ll n){if(n==0) return 1;mint res=modpow(x*x,n/2);if(n&1) res=res*x;return res;}void calc(){calc_inv();calc_product();}using vmint = vector<mint> ;ostream& operator<<(ostream& os, mint a){os << a.a ;return os;}template< typename G >G convert_rooted_tree(const G &g, int r = 0) {int N = (int) g.size();G rg(N);vector< int > v(N);v[r] = 1;queue< int > que;que.emplace(r);while(!que.empty()) {auto p = que.front();que.pop();for(auto &to : g[p]) {if(v[to] == 0) {v[to] = 1;que.emplace(to);rg[p].emplace_back(to);}}}return rg;}main(){INT(n,k);auto _g = make(n);auto g = convert_rooted_tree(_g);calc();vector<vmint> dp(n,vmint(k,1));{auto dfs = [&](auto &&f,int x,int p)->void{for(auto e:g[x]){f(f,e,x);rep(i,k) dp[x][i] *= dp[e][i];}rep(i,k-1) dp[x][i+1] += dp[x][i];};dfs(dfs,0,-1);}mint ans;{auto dfs = [&](auto &&f,int x,int p,vmint res)->void{int m= g[x].size();vector<vmint> l,r;{l.eb(vmint(k,1));r.eb(vmint(k,1));}for(auto e:g[x]){l.eb(vmint(k));rep(i,k){l.back()[i] = l[l.size()-2][i] * dp[e][i];}}reverse(all(g[x]));for(auto e:g[x]){r.eb(vmint(k));rep(i,k){r.back()[i] = r[r.size()-2][i] * dp[e][i];}}if(x)rep2(i,1,k-1) ans += l.back()[i] * res[i-1];elserep(i,k) ans += l.back()[i];reverse(all(g[x]));reverse(all(r));rep(j,g[x].size()){vmint nxt(k);rep(i,k) nxt[i] = l[j][i] * r[j+1][i] * (x ? res[i] : 1);rep(i,k-1) nxt[i+1] += nxt[i];f(f,g[x][j],x,nxt);}};dfs(dfs,0,-1,vmint());}cout<<ans<<endl;}