#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <map>
#include <cstring>
#include <sstream>
#pragma GCC target("popcnt")
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1e9+7;
typedef pair<ld,ld> point;
//#define x first
//#define y second
//#define SEGTREE
//#define TREE
//#define DSU
//#define MATH
#ifdef SEGTREE
template<class Type>
class SegmentTree {
Type (*func)(Type a, Type b);
vector<Type> nodes;
vector<int> l;
vector<int> r;
int size_log2;
Type neutral;
void init_node(int node) {
if(node >= (1 << size_log2))
return;
l[2 * node] = l[node];
r[2 * node] = (l[node] + r[node]) / 2;
init_node(2 * node);
l[2 * node + 1] = (l[node] + r[node]) / 2;
r[2 * node + 1] = r[node];
init_node(2 * node + 1);
nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
}
void update_node(int node) {
if(node < (1 << size_log2))
nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
if(node != 1)
update_node(node / 2);
}
Type get(int node, int ll_, int rr) {
if(rr <= l[node] || ll_ >= r[node])
return neutral;
if(ll_ <= l[node] && rr >= r[node])
return nodes[node];
Type left = get(2 * node, ll_, rr);
Type right = get(2 * node + 1, ll_, rr);
return func(left, right);
}
public:
SegmentTree(Type (*func)(Type a, Type b), vector<Type> vector, Type neutral) : func(func), neutral(neutral) {
size_log2 = 0;
while((1 << size_log2) < vector.size())
size_log2++;
nodes.resize((1 << size_log2) * 2);
l.resize((1 << size_log2) * 2);
r.resize((1 << size_log2) * 2);
for(int i = 0; i < vector.size(); i++)
nodes[(1 << size_log2) + i] = vector[i];
l[1] = 0;
r[1] = 1 << size_log2;
init_node(1);
}
void set(int idx, Type el) {
nodes[(1 << size_log2) + idx] = el;
update_node((1 << size_log2) + idx);
}
Type get(int l, int r) {
return get(1, l, r);
}
Type get(int idx) {
return nodes[(1 << size_log2) + idx];
}
Type get() {
return nodes[1];
}
int get_first_larger_or_eq_than(int bound) {
return get_first_larger_or_eq_than(1, bound);
}
int get_first_larger_or_eq_than(int node, int bound) {
if(node >= (1 << size_log2)) {
return node - (1 << size_log2);
}
if(nodes[node * 2] > bound)
return get_first_larger_or_eq_than(node * 2, bound);
else
return get_first_larger_or_eq_than(node * 2 + 1, bound - nodes[node * 2]);
}
};
#endif
#ifdef TREE
#define POW 18
struct Node {
int parents[POW];
vector<int> conns;
int depth;
int value;
int subtree_depth;
int subtree_size;
int euler;
int val;
int res;
};
ll add(ll a, ll b) {
return a + b;
}
Node nodes[200000];
int n;
int setup(int node, int depth, int euler, ll dist) {
dist += nodes[node].value;
nodes[node].depth = depth;
nodes[node].euler = euler++;
for(int i = 1; i < POW; i++) {
nodes[node].parents[i] = nodes[nodes[node].parents[i - 1]].parents[i - 1];
}
int size = 1;
for(int i = 0; i < nodes[node].conns.size(); i++) {
int child = nodes[node].conns[i];
if(child != nodes[node].parents[0]) {
nodes[child].parents[0] = node;
euler = setup(child, depth + 1, euler, dist);
size += nodes[child].subtree_size;
}
}
nodes[node].subtree_size = size;
return euler;
}
void setup_tree(int root) {
nodes[root].parents[0] = root;
setup(root, 0, 0, 0);
}
int get_subtree_depth(int node) {
if(nodes[node].subtree_depth)
return nodes[node].subtree_depth;
int max_depth = 1;
for(int child : nodes[node].conns) {
if(child == nodes[node].parents[0])
continue;
max_depth = max(max_depth, get_subtree_depth(child) + 1);
}
nodes[node].subtree_depth = max_depth;
return max_depth;
}
int get_parent(int node, int depth) {
if(depth > nodes[node].depth)
return -1;
int climber = node;
for(int i = 0; i < POW; i++) {
if(depth & (1 << i) && climber != -1)
climber = nodes[climber].parents[i];
}
return climber;
}
bool is_sub(int a,int b){
return get_parent(a,nodes[a].depth-nodes[b].depth)==b;
}
int lca(int a, int b) {
if(nodes[a].depth < nodes[b].depth)
swap(a, b);
a = get_parent(a, nodes[a].depth - nodes[b].depth);
if(a == b)
return a;
for(int i = POW - 1; i >= 0; i--) {
if(nodes[a].parents[i] != nodes[b].parents[i]) {
a = nodes[a].parents[i];
b = nodes[b].parents[i];
}
}
return nodes[a].parents[0];
}
#endif
#ifdef DSU
class Dsu {
vector<int> arr;
int num_sets;
public:
Dsu(int size) {
arr = vector<int>(size, -1);
num_sets = size;
}
int merge(int a, int b) {
a = get(a);
b = get(b);
if(a == b)
return a;
if(arr[a] > arr[b])
swap(a, b);
arr[a] += arr[b];
arr[b] = a;
num_sets--;
return a;
}
int get(int a) {
if(arr[a] < 0)
return a;
arr[a] = get(arr[a]);
return get(arr[a]);
}
int get_size(int a) {
return -arr[get(a)];
}
int get_num_sets() {
return num_sets;
}
};
#endif
#ifdef MATH
ll dpf[2000001];
ll factorial(ll n) {
if(n == 0)
return 1;
if(dpf[n])
return dpf[n];
ll result = factorial(n - 1) * n;
result %= MOD;
dpf[n] = result;
return result;
}
ll powm(ll base, ll exp) {
ll result = 1;
for(int i = 0; i < 64; i++) {
if((exp >> i) % 2 == 1) {
result *= base;
result %= MOD;
}
base *= base;
base %= MOD;
}
return result;
}
ll inverse(ll n) {
return powm(n, MOD - 2);
}
ll dpif[2000001];
ll inverse_factorial(ll n) {
if(dpif[n])
return dpif[n];
ll result = inverse(factorial(n));
dpif[n] = result;
return result;
}
ll choose(ll n, ll k) {
return (((factorial(n)*inverse_factorial(n-k))%MOD)*inverse_factorial(k))%MOD;
}
ll gcd(ll a, ll b){
if(a==b)
return a;
if(a<b)
swap(a,b);
if(b==0)
return a;
return gcd(b, a%b);
}
#endif
int n,m,k;
vector<int>children[100001];
vector<int>children2[100001];
int fruit_day[100001];
int fruit_juice[100001];
int fruit_day2[100001];
int fruit_juice2[100001];
int curr_node=1;
int max_day;
struct IncreasingArray{
vector<ll>tree;
vector<int>c1,c2,l,r;
int root=-1;
int new_node(){
int node=(int)tree.size();
tree.push_back(0);
c1.push_back(-1);
c2.push_back(-1);
l.push_back(0);
r.push_back(0);
return node;
}
void update_node(int node){
tree[node]=0;
if(c1[node]!=-1)
tree[node]+=tree[c1[node]];
if(c2[node]!=-1)
tree[node]+=tree[c2[node]];
}
ll get_val(int node,int i){
if(node==-1)
return 0;
if(r[node]<=i)
return tree[node];
if(l[node]>=i)
return 0;
return get_val(c1[node],i)+get_val(c2[node],i);
}
void add_val(int node,int i,ll val){
if(l[node]==r[node]-1){
tree[node]+=val;
return;
}
int mid=(l[node]+r[node])/2;
if(i>=mid){
if(c2[node]==-1){
c2[node]=new_node();
l[c2[node]]=mid;
r[c2[node]]=r[node];
}
add_val(c2[node],i,val);
}else{
if(c1[node]==-1){
c1[node]=new_node();
l[c1[node]]=l[node];
r[c1[node]]=mid;
}
add_val(c1[node],i,val);
}
update_node(node);
}
ll remove(int node,int i,ll val){
if(node==-1)
return val;
if(val==0)
return 0;
if(r[node]<=i)
return val;
if(l[node]==r[node]-1){
ll diff=min(val,tree[node]);
tree[node]-=diff;
return val-diff;
}
val=remove(c1[node],i,val);
if(val==0){
update_node(node);
return 0;
}
val=remove(c2[node],i,val);
update_node(node);
return val;
}
vector<pair<int,ll>> collection;
void collect(int node){
if(node==-1)
return;
if(l[node]==r[node]-1){
if(tree[node]==0)
return;
collection.emplace_back(l[node],tree[node]);
return;
}
collect(c1[node]);
collect(c2[node]);
}
public:
IncreasingArray(){
root=new_node();
r[root]=1<<17;
}
void add_array(IncreasingArray&a){
a.collect(a.root);
for(auto i:a.collection)
add_val(root,i.first,i.second);
}
void add_bound(int x,ll s){
s-=get_val(root,x+1);
add_val(root,x,s);
remove(root,x+1,s);
}
ll get(int i){
return get_val(root,i+1);
}
int size(){
return (int)tree.size();
}
void swap_with(IncreasingArray&a){
swap(tree,a.tree);
swap(c1,a.c1);
swap(c2,a.c2);
swap(l,a.l);
swap(r,a.r);
swap(root,a.root);
}
};
IncreasingArray dp[100001];
void init_node(int node,int parent){
if(fruit_juice[node]){
children2[parent].push_back(curr_node);
fruit_day2[curr_node]=fruit_day[node];
fruit_juice2[curr_node]=fruit_juice[node];
parent=curr_node++;
}
for(int ch:children[node]){
init_node(ch,parent);
}
}
void get(int node){
dp[node]=IncreasingArray();
for(int ch:children2[node])
get(ch);
ll res=fruit_juice2[node];
for(int ch:children2[node])
res+=dp[ch].get(fruit_day2[node]);
int biggest_child=-1;
for(int ch:children2[node])
if(biggest_child==-1||dp[biggest_child].size()<dp[ch].size())
biggest_child=ch;
if(biggest_child!=-1)
dp[biggest_child].swap_with(dp[node]);
for(int ch:children2[node])
dp[node].add_array(dp[ch]);
dp[node].add_bound(fruit_day2[node],res);
}
int main(){
ios::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
//freopen("speeding.in","r",stdin);
//freopen("speeding.out","w",stdout);
cin>>n>>m>>k;
for(int i=1;i<n;i++){
int par;
cin>>par;
par--;
children[par].push_back(i);
}
for(int i=0;i<m;i++){
int v,d,w;
cin>>v>>d>>w;
v--;
fruit_day[v]=d;
fruit_juice[v]=w;
}
init_node(0,0);
set<int>s;
for(int i=0;i<curr_node;i++)
s.insert(fruit_day2[i]);
vector<int>v(s.begin(),s.end());
max_day=(int)v.size();
unordered_map<int,int>m;
for(int i=0;i<max_day;i++)
m[v[i]]=i;
for(int i=0;i<curr_node;i++)
fruit_day2[i]=m[fruit_day2[i]];
get(0);
cout<<dp[0].get(max_day-1)<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
71948 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
82436 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
72372 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
83112 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
71948 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
67 ms |
73320 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
71948 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
71948 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
