結果
問題 | No.196 典型DP (1) |
ユーザー | akusyounin2412 |
提出日時 | 2019-02-05 23:53:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 2,729 bytes |
コンパイル時間 | 1,500 ms |
コンパイル使用メモリ | 125,944 KB |
実行使用メモリ | 27,648 KB |
最終ジャッジ日時 | 2025-01-03 00:15:45 |
合計ジャッジ時間 | 4,953 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
# include <iostream> # include <algorithm> #include <array> # include <cassert> #include <cctype> #include <climits> #include <numeric> # include <vector> # include <string> # include <set> # include <map> # include <cmath> # include <iomanip> # include <functional> # include <tuple> # include <utility> # include <stack> # include <queue> # include <list> # include <bitset> # include <complex> # include <chrono> # include <random> # include <limits.h> # include <unordered_map> # include <unordered_set> # include <deque> # include <cstdio> # include <cstring> #include <stdio.h> #include<time.h> #include <stdlib.h> #include <cstdint> #include <cfenv> #include<fstream> //#include <bits/stdc++.h> using namespace std; using LL = long long; using ULL = unsigned long long; long long MOD = 1000000000 + 7; //924844033 1000000000 + 9; constexpr long long INF = numeric_limits<LL>::max(); const double PI = acos(-1); #define fir first #define sec second #define thi third #define debug(x) cerr<<#x<<": "<<x<<'\n' typedef pair<LL, LL> Pll; typedef pair<double, double> Dll; typedef pair<LL, pair<LL, LL>> Ppll; typedef pair<LL, pair<LL, bitset<100001>>> Pbll; typedef pair<LL, pair<LL, vector<LL>>> Pvll; typedef pair<LL, LL> Vec2; struct Tll { LL first, second, third; }; struct Fll { LL first, second, third, fourth; }; typedef pair<LL, Tll> Ptll; #define rep(i,rept) for(LL i=0;i<rept;i++) #define Rrep(i,mf) for(LL i=mf-1;i>=0;i--) LL h, w, n, m, k, t, s, p, q, last, first, cnt, sum, ans,dp[3000][3000], a[330020], b[330000],sub[3000]; string str, ss; bool f[220000]; char c[4000][4000]; int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } }; struct Edge { LL to, cost; }; struct edge { LL from, to, cost; }; vector<vector<Edge>>vec,rvec; vector<edge>ed; vector<LL>v; map<string, LL>ma; set<LL>st; void YN(bool f) { if (f) cout << "YES" << endl; else cout << "NO" << endl; } void yn(bool f) { if (f) cout << "Yes" << endl; else cout << "No" << endl; } void sub_cnt(int cur,int par) { rep(i, vec[cur].size()) { if (vec[cur][i].to == par)continue; sub_cnt(vec[cur][i].to, cur); sub[cur] += sub[vec[cur][i].to]; } sub[cur]++; } void dfs(int cur,int par) { rep(i, vec[cur].size()) { LL v = vec[cur][i].to; if (v == par)continue; dfs(v,cur); vector<LL>table(sub[cur]+1, 0); rep(j, sub[cur] - sub[v]) rep(l, sub[v] + 1) (table[j + l] += dp[cur][j] * dp[v][l]) %= MOD; rep(j, sub[cur])dp[cur][j] = table[j]; } dp[cur][sub[cur]] = 1; } int main() { cin >> n >> k; vec.resize(n); rep(i, n-1) { LL x, y; cin >> x >> y; vec[x].push_back(Edge{ y,0 }); vec[y].push_back(Edge{ x,0 }); } sub_cnt(0, -1); rep(i, n)dp[i][0] = 1; dfs(0,-1); cout << dp[0][k] << endl; return 0; }