#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)
using namespace std;
void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
int pow(int a,int b,int m){int ans=1;while(b){if(b&1){ans=(ans*a)%m;}b>>=1;a=(a*a)%m;}return ans;}
int binpow(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a);}b>>=1;a=(a*a);}return ans;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 100, mxc = 105, inf = 1e18, MX = 1e5 + 10, maxn = 1e5 + 10;
int cost[N][25], dp[N];
vector <int> g[N];
int t[N * 4], b[N * 4], used[N * 4];
int ar[N];
int n;
int s[maxn], p[maxn], tin[maxn], tout[maxn], depth[N];
int head[maxn]; // «голова» тяжелого пути, которому принадлежит v
int timer = 0;
void push(int v, int tl, int tr) {
if(!used[v]) return;
t[v] = max(t[v], b[v]);
//cout << b[v] <<"->"<< tl << endl;
if (tl != tr) {
b[v * 2] = max(b[v * 2], b[v]);
b[v * 2 + 1] = max(b[v * 2 + 1], b[v]);
used[v*2+1]=1;
used[v*2]=1;
}
used[v]=0;
}
void update(int l, int r, int x, int v = 1, int tl = 0, int tr = MX){
push(v, tl, tr);
if (tr < l || r < tl) return;
if(l <= tl && tr <= r){
b[v] = max(b[v], x);
used[v]=1;
push(v, tl, tr);
return;
}else{
int mid=(tl+tr)/2;
update(l, r, x, v * 2, tl, mid);
update(l, r, x, v * 2 + 1, mid + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
int get(int l, int r, int v = 1, int tl = 0, int tr = MX){
push(v, tl, tr);
if (tr < l || tl > r) return 0;
if(l <= tl && tr <= r){
return t[v];
}
int mid=(tl+tr)/2;
return max(get(l, r, v * 2, tl, mid), get(l, r, v * 2 + 1, mid + 1, tr));
}
void sizes(int v = 1, int par = 1) {
s[v] = 1;
for (int &u : g[v]) {
if(u == par)continue;
depth[u] = depth[v] + 1;
sizes(u, v);
s[v] += s[u];
if (s[u] > s[g[v][0]]){
// &u -- это ссылка, так что её легально использовать при swap-е
swap(u, g[v][0]);
}
}
}
void hld(int v = 0, int par = 1) {
tin[v] = timer++;
p[v] = par;
for (int u : g[v]) {
if(u == par)continue;
// если это тяжелый ребенок -- его next нужно передать
// в противном случае он сам является головой нового пути
head[u] = (u == g[v][0] ? head[v] : u);
hld(u, v);
}
tout[v] = timer;
}
int ancestor(int a, int b) {
return tin[a] <= tin[b] && tin[b] < tout[a];
}
void up(int &a, int &b, int x) {
while (!ancestor(head[a], b)) {
update(tin[head[a]], tin[a], x);
a = p[head[a]];
}
}
void upupd(int a, int x) {
int b = 1;
up(a, b, x);
up(b, a, x);
if (!ancestor(a, b))
swap(a, b);
update(tin[a], tin[b], x);
}
/*
void dfs(int v = 1, int par = 1, int time = 1){
dp[v][time] = max(dp[v][time - 1], cost[v][time]);
int sum = 0;
for(auto to : g[v]){
if(to == par)continue;
dfs(to, v, time);
sum += dp[to][time];
}
dp[v][time] = max(dp[v][time], sum + cost[v][time]);
}
* */
main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
for(int i = 2; i <= n; i++){
int a;
cin >> a;
g[a].pb(i);
g[i].pb(a);
}
head[1] = 1;
sizes(1);
hld(1);
vector < array <int, 4> > vp;
for(int i = 1 ; i<= m; i++){
int a, b, c;
cin >> a >> b >> c;
vp.pb({b, -depth[a], a, c});
//cost[a][b] = c;
}
sort(all(vp));
for(auto &[time, dep, a, c] : vp){
int sum = 0;
for(auto to : g[a]){
if(to != p[a])
sum += get(tin[to], tin[to]);
}
//cout << a <<"->"<< sum + c << endl;
upupd(a, sum + c);
}
int sum = 0;
int a = 1;
for(auto to : g[a]){
//cout << to <<"-"<< get(tin[to], tin[to]) << endl;
sum += get(tin[to], tin[to]);
}
for(int i = 1; i <= n; i++){
//cout << get(tin[i], tin[i]) << endl;
}
cout << sum << endl;
}
/*
* Before implementing the problem:
Do I understand the problem correctly?
Which places are tricky? What do I need to remember to implement them correctly?
Which place is the heaviest by implementation? Can I do it simpler?
Which place is the slowest? Where do I need to be careful about constant factors and where I can choose slower but simpler implementation?
----------------------------------
If not AC:
Did you remember to do everything to handle the tricky places you thought about before?
Is the solution correct?
Do I understand the problem correctly?
----------------------------------
If you have a test on which the solution gives wrong answer:
Is the solution doing what it was supposed to do?
Is the problem in the code or in the idea?
*/
Compilation message
magictree.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
133 | main(){
| ^~~~
magictree.cpp: In function 'void fp(std::string)':
magictree.cpp:15:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:15:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
20844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8792 KB |
Output is correct |
| 4 |
Correct |
87 ms |
32184 KB |
Output is correct |
| 5 |
Correct |
77 ms |
32300 KB |
Output is correct |
| 6 |
Correct |
131 ms |
32144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
231 ms |
23504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
