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
77
78
79
80
81
82
83
84
85
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 1000000007ll * 1000000007ll;
const LL Mod = 998244353ll;
const int maxn = 1000002;
inline int getint() {
int r = 0; bool b = true; char c = getchar();
while ('0' > c || c > '9') { if (c == '-') b = false; c = getchar(); }
while ('0' <= c && c <= '9') { r = r * 10 + (c - '0'); c = getchar(); }
if (b) return r;
return -r;
}
LL mx[maxn*4], dis[maxn], T[maxn], ans[maxn], ANS;
int n, ind[maxn*4], clo, dep[maxn], siz[maxn], h[maxn], cnte, son[maxn], L[maxn], R[maxn];
struct edge_T {int to,next; LL w;} edge[maxn];
inline void ins(int x, int y, LL z) {edge[++cnte].to=y;edge[cnte].next=h[x];edge[cnte].w=z;h[x]=cnte;}
void dfs(int now, int deep, LL distance) {
dep[now] = deep;
dis[now] = distance;
siz[now] = 1;
for (int i = h[now]; i; i = edge[i].next) {
dfs(edge[i].to, deep+1, distance + edge[i].w);
siz[now] += siz[edge[i].to];
if (siz[edge[i].to] > siz[son[now]]) son[now] = edge[i].to;
}
}
void change(int now, int l, int r, int pos, LL val) {
if (ind[now] != clo) {ind[now] = clo; mx[now] = val;}
else mx[now] = max(mx[now], val);
if (l == r) return;
else {
int mid = (l + r) >> 1;
if (pos <= mid) change(now << 1, l, mid, pos, val);
else change(now << 1 | 1, mid + 1, r, pos, val);
}
}
LL res;
void query(int now, int l, int r, int ll, int rr) {
if (ind[now] != clo) return;
if (mx[now] <= res) return;
if (ll <= l && r <= rr) res = mx[now];
else {
int mid = (l + r) >> 1;
if (ll <= mid) query(now << 1, l, mid, ll, rr);
if (rr > mid) query(now << 1 | 1, mid + 1, r, ll, rr);
}
}
inline LL QUERY(int l, int r) {res = -INF; query(1, 1, n, l, r); return res;}
void calc(int now, int rt) {
for (int i = h[now]; i; i = edge[i].next) calc(edge[i].to, rt);
int LL = max(1, dep[rt] + L[rt] + dep[rt] - dep[now]);
int RR = min(n, dep[rt] + R[rt] + dep[rt] - dep[now]);
if (LL <= RR) ans[rt] = max(ans[rt], QUERY(LL, RR) - dis[rt] + dis[now] - dis[rt]);
}
void merg(int now, int rt) {
for (int i = h[now]; i; i = edge[i].next) merg(edge[i].to, rt);
change(1, 1, n, dep[now], dis[now]);
}
void solve(int now) {
++clo;
for (int i = h[now]; i; i = edge[i].next) if (edge[i].to != son[now]) solve(edge[i].to);
if (son[now]) solve(son[now]);
for (int i = h[now]; i; i = edge[i].next) if (edge[i].to != son[now]) {calc(edge[i].to, now); merg(edge[i].to, now);}
int LL = max(1, dep[now] + L[now]);
int RR = min(n, dep[now] + R[now]);
if (LL <= RR) ans[now] = max(ans[now], QUERY(LL, RR) - dis[now]);
change(1, 1, n, dep[now], dis[now]);
ANS = (ANS + ans[now] % Mod * T[n - now] % Mod) % Mod;
}
int main() {
freopen("watchdog.in", "r", stdin);
freopen("watchdog.out", "w", stdout);
int x;
n = getint(); T[0] = 1ll;
for (int i = 1; i <= n; ++i) {ans[i] = -1ll; L[i] = getint(); R[i] = getint(); T[i] = T[i-1] * 23333ll % Mod;}
for (int i = 2; i <= n; ++i) {x = getint(); ins(x, i, getint());}
dfs(1, 1, 0);
solve(1);
printf("%lld", ANS);
fclose(stdin);
fclose(stdout);
return 0;
}
|