QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#874306#8127. Slučajna CestaUnforgettablepl0 31ms12516kbC++202.6kb2025-01-27 23:11:482025-01-27 23:11:49

Judging History

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

  • [2025-01-27 23:11:49]
  • 评测
  • 测评结果:0
  • 用时:31ms
  • 内存:12516kb
  • [2025-01-27 23:11:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

template <int MOD=1000000007>
struct Modular {
  int value;
  static const int MOD_value = MOD;

  Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

  Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend Modular mexp(Modular a, long long e) {
    Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
  friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
  friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};


int32_t main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> adj(n+1);
	for(int i=1;i<n;i++){
		int p;
		cin >> p;
		adj[i+1].emplace_back(p);
		adj[p].emplace_back(i+1);
	}
	vector<Modular<>> v(n+1);
	for(int i=1;i<=n;i++){
		int a;cin>>a;
		v[i]=a;
	}
	vector<Modular<>> Expr(n+1);
	{
		Modular<> power = 1;
		for(int i=1;i<=n;i++){
			Expr[i]=(power-1)/(power*(i-1));
			power*=2;
		}
	}
	vector<Modular<>> Scores(n+1);
	function<void(int,int)> dfs = [&](int x,int p){
		Scores[x] = v[x];
		for(int&j:adj[x])if(j!=p){
			dfs(j,x);
			Scores[x] += Scores[j]*Expr[adj[x].size()];
		}
	};
	dfs(1,0);
	vector<Modular<>> ans(n+1);
	function<void(int,int,Modular<>)> dfs2 = [&](int x,int p,Modular<> s){
		ans[x]=v[x]+s*Expr[adj[x].size()+1];
		for(int&j:adj[x])if(j!=p){
			ans[x]+=Scores[j]*Expr[adj[x].size()+1];
		};
		for(int&j:adj[x])if(j!=p){
			dfs2(j,x,ans[x]-Scores[j]*Expr[adj[x].size()+1]);
		};
	};
	dfs2(1,0,0);
	for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 1ms
memory: 3712kb

input:

2
1
307903 536004

output:

575905
500689959

result:

ok all correct

Test #2:

score: 5
Acceptable Answer
time: 1ms
memory: 3584kb

input:

3
1 2
992649 690492 637324

output:

1497226
876301738
188668693

result:

points 0.50 the answer of the first question is correct, but there are mistakes in other answers.

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 3584kb

input:

4
1 2 3
826918 524416 30987 233038

output:

501126006
889825
344181320
547280006

result:

wrong output format Extra information in the output file

Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 1ms
memory: 3584kb

input:

100
1 2 1 4 5 6 7 7 9 9 5 12 5 4 1 16 17 18 18 20 20 22 23 24 25 23 27 28 27 30 31 32 27 34 35 36 37 38 39 39 41 38 43 43 45 46 43 48 49 49 49 48 48 54 55 56 57 57 55 60 60 62 55 64 65 64 67 67 69 69 69 72 37 74 75 76 76 78 76 80 81 82 80 84 85 74 87 87 89 89 91 89 87 94 94 96 97 98 98
754341 720186...

output:

744419112
92458129
796633776
906713019
738813483
44634543
257542414
899681876
998420397
604089252
437373227
966752781
233425519
994847799
870642959
718590095
864717787
487021558
660446535
552956953
526593760
265808098
653590496
456641011
500338841
750980871
168567006
320979429
98218861
659253483
842...

result:

wrong output format Extra information in the output file

Subtask #3:

score: 0
Wrong Answer

Test #54:

score: 0
Wrong Answer
time: 30ms
memory: 8960kb

input:

60000
1 2 2 1 3 4 5 6 9 6 11 11 13 8 4 10 7 10 3 16 12 9 19 15 24 24 27 25 8 16 13 7 20 15 22 28 33 31 20 27 41 17 25 35 39 5 22 34 19 14 49 34 51 31 39 56 55 48 48 14 47 50 58 12 61 41 66 21 62 64 57 32 54 30 30 50 45 40 56 38 38 43 76 44 84 49 59 84 66 45 57 60 47 42 33 54 74 37 59 26 18 101 80 67...

output:

117639703
390818501
202713296
694335166
734075415
131054207
136423330
920754578
460887682
541621383
782453778
709935982
911110370
807737023
341035751
87442579
445030156
235342255
33841054
221704533
73327605
425614210
857691168
55928611
708755485
412927905
131522540
559598816
628788432
235824959
9235...

result:

wrong output format Extra information in the output file

Subtask #4:

score: 0
Wrong Answer

Test #79:

score: 0
Wrong Answer
time: 31ms
memory: 12516kb

input:

100000
1 1 3 4 5 6 7 8 9 10 9 12 13 14 15 14 12 8 19 20 21 20 19 24 24 26 26 28 29 26 31 26 33 34 26 36 36 38 39 40 41 36 4 44 45 46 47 47 49 44 51 52 53 54 53 52 57 58 59 60 61 61 63 61 65 66 67 67 69 70 69 72 59 74 74 76 76 78 79 78 81 82 83 84 85 82 87 87 58 90 91 92 93 91 95 51 97 98 99 99 101 1...

output:

736079324
493813535
376635493
516986516
590942249
525090797
959170558
814024029
725013570
506463223
878670023
152138435
740433723
388810643
592237351
984236875
173984823
367870467
985865808
76631616
287253098
831447523
726533382
247225719
478143261
782915699
512674554
144579184
421421893
523244990
5...

result:

wrong output format Extra information in the output file