結果

問題 No.196 典型DP (1)
ユーザー kyuridenamidakyuridenamida
提出日時 2015-04-26 23:51:10
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 3,846 bytes
コンパイル時間 2,119 ms
コンパイル使用メモリ 183,568 KB
実行使用メモリ 35,472 KB
最終ジャッジ日時 2024-07-05 03:01:11
合計ジャッジ時間 11,776 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘long long int Tree::gen_lca()’:
main.cpp:104:9: 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:9: 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:9: warning: control reaches end of non-void function [-Wreturn-type]
   78 |         }
      |         ^

ソースコード

diff # 

#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