fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int mod = 998244353;
  8.  
  9. struct mint {
  10.   int n;
  11.   mint(int n_ = 0) : n(n_) {}
  12. };
  13.  
  14. mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= mod) a.n -= mod; return a; }
  15. mint operator*(mint a, mint b) { return mint((long long)a.n * b.n % mod); }
  16. mint &operator+=(mint &a, mint b) { return a = a + b; }
  17. mint &operator*=(mint &a, mint b) { return a = a * b; }
  18.  
  19. mint mpow(mint a, int b) {
  20.   mint res = 1;
  21.   for (; b > 0; a *= a, b >>= 1) if (b & 1) res *= a;
  22.   return res;
  23. }
  24.  
  25. mint minv(mint a) {
  26.   return mpow(a, mod - 2);
  27. }
  28.  
  29. struct Foo {
  30.   int u, v;
  31.   mint w;
  32. };
  33.  
  34. vector<Foo> foos;
  35. vector<int> g[240];
  36. int n;
  37.  
  38. void dfs(int u, int p = -1) {
  39.   int cnt = 0;
  40.   for (int v : g[u]) if (v != p) {
  41.     dfs(v, u);
  42.     cnt++;
  43.   }
  44.   for (int v : g[u]) if (v != p) {
  45.     foos.push_back((Foo){u, v, minv(cnt)});
  46.   }
  47.   int xu = cnt == 0 ? u : u + n;
  48.   int xv = p == 0 ? p : p + n;
  49.   foos.push_back((Foo){xu, xv, 1});
  50. }
  51.  
  52. int main() {
  53.   cin >> n;
  54.   for (int i = 0; i < n - 1; i++) {
  55.     int u, v;
  56.     cin >> u >> v;
  57.     u--;
  58.     v--;
  59.     g[u].push_back(v);
  60.     g[v].push_back(u);
  61.   }
  62.   int m;
  63.   cin >> m;
  64.   vector<int> t(m);
  65.   for (int i = 0; i < m; i++) {
  66.     cin >> t[i];
  67.   }
  68.   sort(t.rbegin(), t.rend());
  69.   int q;
  70.   cin >> q;
  71.   dfs(0, -1);
  72.   vector<mint> ans(n * 2);
  73.   vector<mint> p0(n * 2);
  74.   vector<mint> p1(n * 2);
  75.   for (int i = 1; i <= q; i++) {
  76.     while (!t.empty() && t.back() == i) {
  77.       p0[0] += 1;
  78.       t.pop_back();
  79.     }
  80.     for (int i = 0; i < n * 2; i++) {
  81.       ans[i] += p0[i];
  82.       p1[i] = 0;
  83.     }
  84.     for (Foo f : foos) {
  85.       p1[f.v] += p0[f.u] * f.w;
  86.     }
  87.     swap(p0, p1);
  88.   }
  89.   for (int i = 0; i < n; i++) {
  90.     ans[i] += ans[i + n];
  91.     printf("%d ", ans[i].n);
  92.   }
  93.   puts("");
  94. }
  95.  
Runtime error #stdin #stdout #stderr 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/HnoH73
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!