设 \(f_{u,i}\) 表示第 \(i\) 天收获 \(u\) 点时 \(u\) 子树内的答案。
考虑合并 \(u\) 和儿子 \(v\) 的答案。
有 \[
f'_{u,i} = \max\{\max\limits_{j=0}^i\{f_{u,i}+f_{v,j}\}.\max\limits_{j=0}^i\{f_{u,j}+f_{v,i}\}\}
\]
发现是一个 max 卷积的形式，可以考虑使用线段树合并维护。
复杂度 \(O(n \log n)\)。
代码： 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
const int N = 1e5;
int n,m,k;
int d[N + 5],w[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
namespace SEG
{
struct node
{
long long val,tag;
int ls,rs;
} seg[(N << 6) + 5];
inline void push(int p)
{
if(seg[p].tag)
{
if(seg[p].ls)
seg[seg[p].ls].val += seg[p].tag,
seg[seg[p].ls].tag += seg[p].tag;
if(seg[p].rs)
seg[seg[p].rs].val += seg[p].tag,
seg[seg[p].rs].tag += seg[p].tag;
seg[p].tag = 0;
}
}
void insert(int x,long long k,int &p,int tl,int tr)
{
static int tot = 0;
!p && (seg[p = ++tot] = seg[0],1),seg[p].val = max(seg[p].val,k);
if(tl == tr)
return ;
push(p);
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
long long query(int r,int p,int tl,int tr)
{
if(!p || r >= tr)
return seg[p].val;
push(p);
int mid = tl + tr >> 1;
long long ret = -0x3f3f3f3f3f3f3f3f;
ret = max(ret,query(r,seg[p].ls,tl,mid));
r > mid && (ret = max(ret,query(r,seg[p].rs,mid + 1,tr)));
return ret;
}
long long val(int x,int p,int tl,int tr)
{
if(tl == tr)
return seg[p].val;
push(p);
int mid = tl + tr >> 1;
return x <= mid ? val(x,seg[p].ls,tl,mid) : val(x,seg[p].rs,mid + 1,tr);
}
int merge(int p,int q,long long ptag,long long qtag,int tl,int tr)
{
if(!p && !q)
return 0;
if(!p)
{
seg[q].val += qtag,seg[q].tag += qtag;
return q;
}
if(!q)
{
seg[p].val += ptag,seg[p].tag += ptag;
return p;
}
if(tl == tr)
{
ptag = max(ptag,seg[q].val),qtag = max(qtag,seg[p].val);
seg[p].val = max(seg[p].val + ptag,seg[q].val + qtag);
return p;
}
push(p),push(q);
int mid = tl + tr >> 1;
long long plval = seg[seg[p].ls].val;
long long qlval = seg[seg[q].ls].val;
seg[p].ls = merge(seg[p].ls,seg[q].ls,ptag,qtag,tl,mid);
seg[p].rs = merge(seg[p].rs,seg[q].rs,max(ptag,qlval),max(qtag,plval),mid + 1,tr);
seg[p].val = max(seg[seg[p].ls].val,seg[seg[p].rs].val);
return p;
}
}
int fa[N + 5];
int rt[N + 5];
void dfs(int p)
{
for(register int i = first[p];i;i = pre[i])
dfs(to[i]),
rt[p] = SEG::merge(rt[p],rt[to[i]],0,0,1,N);
d[p] && (SEG::insert(d[p],w[p] + max(SEG::query(d[p],rt[p],1,N),0LL),rt[p],1,N),1);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(register int i = 2;i <= n;++i)
scanf("%d",fa + i),add(fa[i],i);
int x,y,z;
for(register int i = 1;i <= m;++i)
scanf("%d%d%d",&x,&y,&z),d[x] = y,w[x] = z;
dfs(1);
printf("%lld\n",SEG::seg[rt[1]].val);
}