結果

問題 No.196 典型DP (1)
コンテスト
ユーザー kyuridenamida
提出日時 2015-04-27 00:51:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 4,601 bytes
コンパイル時間 2,587 ms
コンパイル使用メモリ 182,148 KB
実行使用メモリ 35,456 KB
最終ジャッジ日時 2024-07-05 03:23:35
合計ジャッジ時間 10,775 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 41
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘long long int Tree::gen_lca()’:
main.cpp:104:5: warning: no return statement in function returning non-void [-Wreturn-type]
  104 |     }
      |     ^
main.cpp: In member function ‘long long int Tree::dfs(const std::vector<std::vector<long long int> >&)’:
main.cpp:122:5: warning: no return statement in function returning non-void [-Wreturn-type]
  122 |     }
      |     ^
main.cpp: In function ‘long long int dfs(long long int)’:
main.cpp:161:1: warning: no return statement in function returning non-void [-Wreturn-type]
  161 | }
      | ^
main.cpp: In member function ‘bool Tree::verify()’:
main.cpp:78:5: warning: control reaches end of non-void function [-Wreturn-type]
   78 |     }
      |     ^

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define int long long

long long gcd(long long a,long long b){
    return b ? gcd(b,a%b) : a;
}
long long lcm(long long a,long long b){
    return a / gcd(a,b) * b;
}

long long mul(long long a,long long b,const long long mod){
    return b?(mul(a*2,b/2,mod)+(b&1?a:0))%mod:0;
}

long long bpow(long long a,long long b,const long long mod){
    return (b?bpow(a*a%mod,b/2,mod)*(b&1?a:1):1)%mod;
}

long long inv(long long a,const long long mod){
    return bpow(a,mod-2,mod);
}

// to overflow
/*long long bpow(long long a,long long b,const long long mod){
    return (b?mul(bpow(mul(a,a,mod),b/2,mod),(b&1?a:1),mod):1)%mod;
}*/
class mInt{
public:
    static const long long mod = 1000000007;
    long long v;
    mInt():v(0){}
    mInt(long long v):v((v%mod+mod)%mod){}
};
mInt& operator += (mInt &a,mInt b){ return a = a.v + b.v; }
mInt& operator -= (mInt &a,mInt b){ return a = a.v - b.v; }
mInt& operator *= (mInt &a,mInt b){ return a = a.v * b.v; }
mInt& operator /= (mInt &a,mInt b){ return a = a.v * inv(b.v,mInt::mod); }
mInt operator + (mInt a,mInt b){ return a += b; }
mInt operator - (mInt a,mInt b){ return a -= b; }
mInt operator * (mInt a,mInt b){ return a *= b; }
mInt operator / (mInt a,mInt b){ return a /= b; }
ostream& operator<<(ostream& os, const mInt& x){ return os << x.v; }


class Tree{
public:
    Tree(){}
    //[0,n)
    int n,logn,root;
    vector<vector<int>> child;
    vector<vector<int>> parent;
    vector<pair<int,int>> edges;
    vector<int> depth;
    Tree(int n_,vector<pair<int,int>> es,int root) : root(root){
        edges = es;
        n = n_;
        logn = 0;
        while(n_){
            ++logn;
            n_ /= 2;
        }
        parent.resize(logn,vector<int>(n,-1));
        depth.resize(n,-1);
        child.resize(n);
        vector<vector<int>> g(n);
        for( auto e : es ){
            g[e.first].push_back(e.second);
            g[e.second].push_back(e.first);
        }
        dfs(g);
        gen_lca();
        verify();
    }
    bool verify(){
        for(int i = 0 ; i < n ; i++)
            assert( depth[i] != -1 );
    }
    int lca(int x,int y){
        if( depth[x] < depth[y] )swap(x,y);
        int d = depth[x] - depth[y];
        for(int i = 0 ; i < logn ; i++)
            if( d >> i & 1 ) x = parent[i][x];
        if( x == y ) return x;
        
        for(int i = logn-1 ; i >= 0 ; i--){
            if( parent[i][x] != parent[i][y] ){
                x = parent[i][x];
                y = parent[i][y];
            }
        }
        return parent[0][x];
    }
    int distance(int x,int y){
        return depth[x] + depth[y] - 2 * depth[lca(x,y)];
    }
private:
    int gen_lca(){
        for(int i = 1 ; i < logn ; i++){
            for(int j = 0 ; j < n ; j++)
                if( parent[i-1][j] != -1 ) 
                    parent[i][j] = parent[i-1][parent[i-1][j]];
        }
    }
    int dfs(const vector<vector<int>> &g){
        stack< array<int,3> > S;
        S.push(array<int,3>{root,-1,0});
        while( S.size() ){
            int x = S.top()[0];
            int p = S.top()[1];
            int d = S.top()[2];
            S.pop();
            parent[0][x] = p;
            depth[x] = d;
            for( auto e : g[x] ){
                if( e != p ){
                    S.push(array<int,3>{e,x,d+1});
                    child[x].push_back(e);
                }
            }
        }
    }
};

mInt dp[2010][2010];
int sub[2010];
Tree tr;
int subtree(int x){
    if( sub[x] != 0 ) return sub[x];
    for(auto c : tr.child[x] ){
        sub[x] += subtree(c);
    }
    return sub[x] += 1;
}
int dfs(int x){
    int s = subtree(x);
    dp[x][0] = 1;
    for(auto c : tr.child[x] ){
        dfs(c);
        mInt dp2[s+1];
        mInt tot[s+1];
        int ss = subtree(c);
        for(int k = 0 ; k <= s ; k++){
            tot[k] = dp[x][k];
            if(k) tot[k] += tot[k-1];
        }
        for(int k = 0 ; k <= ss ; k++){
            if( dp[c][k].v > 0 ){
                for(int j = s ; j >= k ; j--){
                   dp2[j] += dp[c][k] * dp[x][j-k];
                }
            }
        }
        for(int k = 0 ; k <= s ; k++){
            dp[x][k] = dp2[k];
            //if( k == 6 ) cout << dp[x][k] << "<" << x << endl;
        }
    }
    dp[x][subtree(x)] += 1;
    
}
signed main(){
    int N,K;
    cin >> N >> K;
    vector< pair<int,int> > es;
    for(int i = 0 ; i+1 < N ; i++){
        int a,b;
        cin >> a >> b;
        es.push_back({a,b});
    }
    tr = Tree(N,es,0);
    dfs(0);
    cout << dp[0][K] << endl;
}
0