結果

問題 No.1075 木の上の山
ユーザー noiminoimi
提出日時 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); }
      |                      ~~~~~^~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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&...){}
#endif
struct 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];
else
rep(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0