QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387770#7792. Tree Topological Order CountingJCY_5 124ms51004kbC++142.4kb2024-04-12 19:51:482024-04-12 19:51:49

Judging History

你现在查看的是最新测评结果

  • [2024-04-12 19:51:49]
  • 评测
  • 测评结果:5
  • 用时:124ms
  • 内存:51004kb
  • [2024-04-12 19:51:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
constexpr int MAXN = 5010, MOD = 1e9 + 7;
void inc(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
int qpow(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = (ll)x * x % MOD)
    if (y & 1) ret = (ll)ret * x % MOD;
  return ret;
}
int n, fa[MAXN], sz[MAXN], wys[MAXN], iwys[MAXN], inv[MAXN], dp[MAXN][MAXN];
int fac[MAXN], ifac[MAXN], ans[MAXN], b[MAXN];
vector<int> g[MAXN];
int C(int x, int y) { return (ll)fac[x] * ifac[y] % MOD * ifac[x - y] % MOD; }
void dfs(int u, int lb) {
  int rb = n - sz[u] + 1;
  for (int i = lb + 1; i <= rb; ++i) inc(dp[u][i], dp[u][i - 1]);
  int coef = (ll)wys[u] * sz[u] % MOD * fac[sz[u] - 1] % MOD;
  for (int i = lb; i <= rb; ++i) {
    ans[u] = (ans[u] + (ll)dp[u][i] * C(rb - i + sz[u] - 1, rb - i) % MOD *
                           coef * b[i]) %
             MOD;
  }
  for (auto v : g[u]) {
    coef = (ll)wys[u] * iwys[v] % MOD * sz[u] % MOD * fac[sz[u] - sz[v] - 1] % MOD;
    for (int x = lb; x <= rb; ++x) {
      dp[v][x + 1] = (ll)dp[u][x] * C(rb - x + sz[u] - sz[v] - 1, rb - x) %
                     MOD * coef % MOD;
    }
    dfs(v, lb + 1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 2; i <= n; ++i) {
    cin >> fa[i];
    g[fa[i]].emplace_back(i);
  }
  for (int i = 1; i <= n; ++i) cin >> b[i];
  fill(sz + 1, sz + n + 1, 1);
  for (int i = n; i >= 2; --i) sz[fa[i]] += sz[i];
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % MOD;
  ifac[n] = qpow(fac[n], MOD - 2);
  for (int i = n - 1; i >= 0; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % MOD;
  for (int i = 1; i <= n; ++i) inv[i] = (ll)ifac[i] * fac[i - 1] % MOD;
  for (int i = 1; i <= n; ++i) {
    wys[i] = inv[sz[i]];
    iwys[i] = sz[i];
  }
  for (int i = n; i >= 2; --i) {
    wys[fa[i]] = (ll)wys[fa[i]] * wys[i] % MOD;
    iwys[fa[i]] = (ll)iwys[fa[i]] * iwys[i] % MOD;
  }
  dp[1][1] = 1;
  dfs(1, 1);
  for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
  return 0;
}
/*
g++ C.cpp -o C -std=c++14 -O2 -Wall -Wextra -Wshadow -g
-fsanitize=address,undefined
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 3792kb

input:

10
1 2 2 4 2 5 3 2 3
421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543

output:

132551152 750202542 844925059 844925059 320019016 837104208 346368542 333193779 837104208 333193779

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

10
1 2 2 4 5 4 3 7 1
226457597 222460848 126601784 27445914 811511381 52803670 776934531 832659037 955599897 927944188

output:

802913206 192357888 80729172 288305444 609011662 689888737 609011662 673713322 689888737 479113328

result:

ok 10 numbers

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 3868kb

input:

20
1 1 1 4 2 5 2 5 4 6 4 7 11 11 2 9 7 2 9
305559508 68914843 154933697 736516347 250860247 264123902 632865608 32202124 861284820 505164728 564475479 136404892 645017283 837805203 802302363 50345521 511083407 292719502 356887812 390453540

output:

4420887 788130909 277088290 329621633 157393474 42292358 346897100 706626195 346897100 468004133 556186525 468004133 982694311 614012945 614012945 706626195 982694311 982694311 706626195 982694311

result:

wrong answer 2nd numbers differ - expected: '270322976', found: '788130909'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 124ms
memory: 51004kb

input:

3000
1 1 3 1 3 6 1 5 3 2 4 9 6 7 2 7 1 1 8 1 4 17 23 2 5 24 15 12 14 28 16 32 33 16 6 1 3 12 17 31 33 19 43 3 33 7 35 42 23 15 30 12 8 21 16 38 53 8 49 56 21 25 30 54 30 14 20 10 35 28 35 55 12 50 10 1 75 76 19 22 8 82 4 68 42 9 57 68 3 67 56 8 11 23 72 68 9 62 32 20 73 39 74 56 88 61 83 78 69 29 29...

output:

16671810 -843657953 87777176 120631638 994334708 392328975 -97702321 -361651179 70301131 -790689261 -974896336 115084367 486276080 873818471 253115929 -494099758 148672394 320815418 4052622 758818977 -970353819 -552397166 -727205520 -492913882 831628583 593172088 328309069 452848085 -202090130 -1067...

result:

wrong answer 2nd numbers differ - expected: '944499931', found: '-843657953'

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%