Submission #64701

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define log_2(a) (log((a)) / log(2))
#define ln '\n'
using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;
static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 998244353;
static const int SIZE = 200005;
LL treeDP(int pos, int parCount);
vector<int> tree[SIZE];
bool isVisited[SIZE];
LL parCnt[SIZE];
LL enh[SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, Q;
cin >> N >> Q;
for(int i = 0; i < N - 1; ++i) {
int a, b;
cin >> a >> b;
tree[a].pb(b);
tree[b].pb(a);
}
treeDP(1, 0);
LL res = 0;
while(Q--) {
LL x, v;
cin >> x >> v;
res += enh[x] * v % MOD;
res %= MOD;
cout << res << '\n';
}
return 0;
}
LL treeDP(int pos, int parCount) {
if(isVisited[pos]) {
return 0;
}
isVisited[pos] = true;
LL sum = 0;
for(int v : tree[pos]) {
sum += treeDP(v, parCount + 1);
sum %= MOD;
}
enh[pos] = (sum + (parCount + 1)) % MOD;
return enh[pos];
}

ステータス

項目 データ
問題 1412 - RAQ on Tree
ユーザー名 crom
投稿日時 2020-11-11 23:08:45
言語 C++14
状態 Accepted
得点 5
ソースコード長 1545 Byte
最大実行時間 142 ms
最大メモリ使用量 66352 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 31 ms 6620 KB
1
in02.txt AC 20 ms 6488 KB
1
in03.txt AC 55 ms 9688 KB
1
in04.txt AC 98 ms 15956 KB
1
in05.txt AC 130 ms 18540 KB
1
in06.txt AC 129 ms 20356 KB
1
in07.txt AC 125 ms 22300 KB
1
in08.txt AC 126 ms 24248 KB
1
in09.txt AC 94 ms 26692 KB
1
in10.txt AC 96 ms 28572 KB
1
in11.txt AC 100 ms 30576 KB
1
in12.txt AC 107 ms 32456 KB
1
in13.txt AC 71 ms 29224 KB
1
in14.txt AC 60 ms 35080 KB
1
in15.txt AC 142 ms 42708 KB
1
in16.txt AC 141 ms 47700 KB
1
in17.txt AC 133 ms 48968 KB
1
in18.txt AC 121 ms 54072 KB
1
in19.txt AC 128 ms 56032 KB
1
in20.txt AC 136 ms 57864 KB
1
in21.txt AC 137 ms 47408 KB
1
in22.txt AC 125 ms 49316 KB
1
in23.txt AC 125 ms 51228 KB
1
in24.txt AC 109 ms 53136 KB
1
in25.txt AC 123 ms 55300 KB
1
in26.txt AC 53 ms 49048 KB
1
in27.txt AC 51 ms 50324 KB
1
in28.txt AC 23 ms 50320 KB
1
in29.txt AC 63 ms 52248 KB
1
in30.txt AC 58 ms 54424 KB
1
in31.txt AC 134 ms 64408 KB
1
in32.txt AC 122 ms 66352 KB
1
sample01.txt AC 23 ms 58316 KB
1
sample02.txt AC 25 ms 58320 KB
1