結果
問題 | 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;elsecout << "NO" << endl;}void yn(bool f) {if (f)cout << "Yes" << endl;elsecout << "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;}