結果
問題 | No.1075 木の上の山 |
ユーザー |
![]() |
提出日時 | 2020-06-05 22:52:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 222 ms / 2,000 ms |
コード長 | 3,679 bytes |
コンパイル時間 | 1,031 ms |
コンパイル使用メモリ | 83,980 KB |
実行使用メモリ | 34,988 KB |
最終ジャッジ日時 | 2024-12-17 17:07:43 |
合計ジャッジ時間 | 3,914 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#define llint long long#define inf 1e18#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define mod 1000000007using namespace std;typedef pair<llint, llint> P;llint n, k;vector<llint> G[1005];typedef pair<llint, llint> P;int parent[1005];llint dp[1005][1005], dp2[1005][1005];llint sum[1005][1005], sum2[1005][1005];llint get(int u, int v, int x){if(parent[u] == v) return dp2[u][x];else return dp[v][x];}llint getsum(int u, int v, int x){if(parent[u] == v) return sum2[u][x];else return sum[v][x];}void dfs(int v, int p){parent[v] = p;for(int i = 0; i < G[v].size(); i++){if(G[v][i] == p) continue;dfs(G[v][i], v);}for(int j = 1; j <= k; j++){llint mul = 1;for(int i = 0; i < G[v].size(); i++){int u = G[v][i];if(u == p) continue;mul *= getsum(v, u, j), mul %= mod;}dp[v][j] = mul;sum[v][j] = sum[v][j-1] + dp[v][j], sum[v][j] %= mod;}}llint lsum[1005], rsum[1005];void dfs2(int v, int p){llint m = G[v].size(), mul;for(int j = 1; j <= k; j++){mul = lsum[0] = 1;for(int i = 0; i < m; i++){int u = G[v][i];mul *= getsum(v, u, j), mul %= mod; //lsum[i+1] = mul;}mul = rsum[m+1] = 1;for(int i = m-1; i >= 0; i--){int u = G[v][i];mul *= getsum(v, u, j), mul %= mod; //rsum[i+1] = mul;}for(int i = 0; i < m; i++){int u = G[v][i];if(u == p) continue;dp2[u][j] = lsum[i] * rsum[i+2] % mod;sum2[u][j] = (sum2[u][j-1] + dp2[u][j]) % mod;}}for(int i = 0; i < G[v].size(); i++){if(G[v][i] == p) continue;dfs2(G[v][i], v);}}int size[1005];bool used[1005];int sizedfs(int v, int pre){int ret = 1;for(int i = 0; i < G[v].size(); i++){if(G[v][i] == pre) continue;if(used[G[v][i]]) continue;ret += sizedfs(G[v][i], v);}return size[v] = ret;}int centdfs(int v, int pre, int sz){for(int i = 0; i < G[v].size(); i++){if(G[v][i] == pre) continue;if(used[G[v][i]]) continue;if(size[G[v][i]] > sz/2) return centdfs(G[v][i], v, sz);}return v;}llint calcdfs(llint v, llint p, llint k){llint ret = 0;if(p != -1) ret = getsum(p, v, k-1);llint mul = 1;for(int i = 0; i < G[v].size(); i++){llint u = G[v][i];if(u == p) continue;if(used[u]){mul *= getsum(v, u, k-1), mul %= mod;continue;}mul *= calcdfs(G[v][i], v, k), mul %= mod;}ret += mul, ret %= mod;return ret;}llint ans = 0;void solve(int v){sizedfs(v, -1);v = centdfs(v, -1, size[v]);/* 処理 */for(int i = 2; i <= k; i++){ans += calcdfs(v, -1, i);ans %= mod;}used[v] = true;for(int i = 0; i < G[v].size(); i++){if(used[G[v][i]]) continue;solve(G[v][i]);}}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;llint u, v;for(int i = 1; i <= n-1; i++){cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}if(k == 1){cout << 1 << endl;return 0;}dfs(1, -1);dfs2(1, -1);/*for(int i = 1; i <= n; i++){for(int j = 0; j < G[i].size(); j++){cout << i << " " << G[i][j] << " : ";for(int l = 1; l <= k; l++){cout << get(i, G[i][j], l) << " ";}cout << endl;}}*/solve(1);ans += 1, ans %= mod;cout << ans << endl;return 0;}