QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#403409 | #8126. Restorani | lfxxx# | 0 | 61ms | 43064kb | C++14 | 2.0kb | 2024-05-02 11:05:05 | 2024-05-02 11:05:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 1e6 + 5, mod = 1e9 + 7;
vector<int>e[N];
int n, a[N], dp[N], tp[N], ans[N];
inline int qpow(int b, int k)
{
int res = 1;
while (k) {
if (k & 1) res = (ll) res * b % mod;
b = (ll) b * b % mod;
k >>= 1;
}
return res;
}
void dfs1(int u, int f)
{
int c = e[u].size() - (u != f);
dp[u] = a[u];
for (int v : e[u]) {
if (v != f) {
dfs1(v, u);
dp[u] = (dp[u] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) % mod * dp[v]) % mod;
}
}
}
void hg(int u, int v)
{
int c = e[u].size();
dp[u] = (dp[u] - a[u]) % mod;
dp[u] = (dp[u] - (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) * dp[v]) % mod;
dp[u] = (ll) dp[u] * 2 % mod * (tp[c - 1] - 1) % mod * c % mod * qpow((ll) (tp[c] - 1) * (c - 1) % mod, mod - 2) % mod;
dp[u] = (dp[u] + a[u]) % mod;
c = e[v].size();
dp[v] = (dp[v] - a[v]) % mod;
dp[v] = (ll) dp[v] * (tp[c] - 1) % mod * (c - 1) % mod * qpow(2ll * (tp[c - 1] - 1) % mod * c % mod, mod - 2) % mod;
dp[v] = (dp[v] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) % mod * dp[u]) % mod;
dp[v] = (dp[v] + a[v]) % mod;
}
void dfs2(int u, int f)
{
ans[u] = (dp[u] + mod) % mod;
for (int v : e[u]) {
if (v != f) {
hg(u, v);
dfs2(v, u);
hg(v, u);
}
}
}
bool en;
int main()
{
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 2; i <= n; ++i) {
int f;
cin >> f;
e[f].emplace_back(i);
e[i].emplace_back(f);
}
for (int i = 1; i <= n; ++i) cin >> a[i];
tp[0] = 1;
for (int i = 1; i <= n; ++i) {
tp[i] = tp[i - 1] * 2ll % mod;
}
dfs1(1, 1);
dfs2(1, 1);
for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Acceptable Answer
time: 0ms
memory: 35484kb
input:
1 1 1 1
output:
1
result:
points 0.30
Test #2:
score: 0
Wrong Answer
time: 5ms
memory: 34640kb
input:
5 3 3 1 2 4 2 1 1 2 2 3 3 4 4 5
output:
500000008 0 0 3 0
result:
wrong answer
Subtask #2:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 61ms
memory: 43064kb
input:
300000 100000 109370 205978 224742 196992 72895 175835 177858 199406 235175 124763 18605 240852 170753 234091 260042 224910 164378 18209 253733 55514 99033 39740 131545 58235 237944 168314 28570 283886 209944 126973 228465 187033 94132 153369 248330 47334 58875 113999 224027 260133 131708 288915 269...
output:
500125004 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer
Subtask #3:
score: 0
Wrong Answer
Test #46:
score: 0
Wrong Answer
time: 6ms
memory: 29548kb
input:
5000 2000 4078 2691 3285 4560 722 2633 1060 29 771 12 1702 164 4924 4572 906 2334 2800 3353 610 3939 4869 2690 3185 2079 2738 199 1926 2000 4985 39 1504 7 1350 3735 4371 1992 4196 555 393 2320 2194 114 831 28 424 1355 2010 3279 4932 3450 4345 4991 2758 96 2884 4840 1778 92 1691 256 666 792 3757 1986...
output:
875002075 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer
Subtask #4:
score: 0
Wrong Answer
Test #96:
score: 0
Wrong Answer
time: 61ms
memory: 41056kb
input:
300000 100000 297688 58574 11154 227659 2832 4187 46902 30386 123954 297021 107275 50042 254278 246399 245777 174442 294196 213936 66372 33303 196079 68308 279926 155894 38996 65379 16366 236135 73779 90307 140452 79063 170940 175005 103283 242495 199312 112374 299718 3222 294033 126886 258651 54878...
output:
716006258 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer