QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403408#8126. Restoranilfxxx#0 78ms39220kbC++142.0kb2024-05-02 11:04:202024-05-02 11:04:20

Judging History

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

  • [2024-05-02 11:04:20]
  • 评测
  • 测评结果:0
  • 用时:78ms
  • 内存:39220kb
  • [2024-05-02 11:04:20]
  • 提交

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: 7ms
memory: 27228kb

input:

1 1
1
1

output:

1

result:

points 0.30

Test #2:

score: 0
Wrong Answer
time: 3ms
memory: 27224kb

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: 78ms
memory: 39056kb

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: 4ms
memory: 27520kb

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: 60ms
memory: 39220kb

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