Submission #938921

#	Time	Username	Problem	Language	Result	Execution time	Memory
938921		vjudge1	Magic Tree (CEOI19_magictree)	C++17	14 / 100	195 ms	25428 KiB

magictree

/*adid_r10*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N = 1e5 + 9, MOD = 1e9 + 7;
    
//// Total Code time complexity: O(nlogn)



////
    
int k;
// int a[N];
struct ST {
  ll t[4 * N];
  static const int inf = 1e9;
  ST() {
    memset(t, 0, sizeof t);
  }
  void build(int _n, int b, int e) {
    if (b == e) {
      t[_n] = 0;
      return;
    }
    int mid = (b + e) >> 1, l = _n << 1, r = l | 1;
    build(l, b, mid);
    build(r, mid + 1, e);
    t[_n] = max(t[l], t[r]); // change this
  }
  void upd(int _n, int b, int e, int i, ll x) {
    if (b > i || e < i) return;
    if (b == e && b == i) {
      t[_n] = x; // update
      return;
    }
    int mid = (b + e) >> 1, l = _n << 1, r = l | 1;
    upd(l, b, mid, i, x);
    upd(r, mid + 1, e, i, x);
    t[_n] = max(t[l], t[r]); // change this
  }
  void upd (int idx, int x) {
    upd(1, 1, k, idx, x);
  }

  ll query(int _n, int b, int e, int i, int j) {
    if (b > j || e < i) return 0; // return appropriate value
    if (b >= i && e <= j) return t[_n];
    int mid = (b + e) >> 1, l = _n << 1, r = l | 1;
    return max(query(l, b, mid, i, j), query(r, mid + 1, e, i, j)); // change this
  }
  ll query(int l, int r) {
    return query (1, 1, k, l, r);
  }
}seg;
///

vector <int> adj[N];
int sz[N];

int TM = 1;
int st [N], ft[N], node_start[N];
void dfsz_and_eulerTour (int u, int p) {
    sz[u] = 1;
    node_start[TM] = u;
    st[u] = TM++;
    for (auto v: adj[u]) {
        if (v != p) {
            dfsz_and_eulerTour (v, u);
            sz[u] += sz[v];
        }
    }
    ft[u] = TM;
}
int dd[N], ww[N];
void ddffss (int u, int p, ST &seg) {

    for (auto v: adj[u]) {
        if (v != p) {
            ddffss(v, u, seg);
        }
    }
    if(dd[u] == 0) return;
    seg.upd(dd[u], 0LL + seg.query(1, dd[u]) + ww[u]);
}

ll ans[N];
void dfs (int u, int p, bool keep, ST &seg) {
    int mxsz = -1, bigchild = -1;
    for (auto v: adj[u]) {
        if (v != p) {
            if (sz[v] > mxsz) {
                mxsz = sz[v];
                bigchild = v;
            }
        
        }
    }

    for (auto v: adj[u]) {
        if (v != p && v != bigchild) {
            dfs(v, u, 0, seg);
            ans[u] += ans[v];
        }
    }
    if (bigchild != -1) {
        dfs(bigchild, u, 1, seg);
        ans[u] += ans[bigchild];
    }
    
    for (auto v: adj[u]) {
        if (v != p && v != bigchild) {
            // for (int t = st[v]; t < ft[v]; t++) {
            //     // OPS(node_start[t], mxfrq, sum);
            //     // colcnt[col[node_start[t]]]++;

            // }
            ddffss (v, p, seg);
        } 
    }
    if (dd[u] != 0) {
        seg.upd(dd[u], seg.query (1, dd[u]) + ww[u]);
        ans[u] = max(ans[u], 1LL * seg.query (1, dd[u]));
    }
    // OPS(u, mxfrq, sum);
    // colcnt[col[u]]++;    
    //now colcnt[c] is the number of vertices in subtree of vertex u that has color c. You can answer the queries 

    if (keep == 0) {
        for (int t = st[u]; t < ft[u]; t++) {
            int cc = node_start[t];
            // colcnt[col[cc]]--;
            if (dd[cc] == 0) continue;
            seg.upd(dd[cc], 0);
        }
    }
}

int32_t main () {
    ios_base::sync_with_stdio(0);cin.tie(0);
    // cout << "YO\n";
    // return 0;
    int nn, mm, kk; cin >> nn >> mm >> kk;
    k = kk;
    seg.build(1, 1, k);
    // cout << "YO\n";
    for (int i = 2; i <= nn; i++) {
        int p; cin >> p;
        adj[p].push_back(i);
    }   

    for (int i = 1; i <= mm; i++) {
        int v, d, w; cin >> v >> d >> w;
        dd[v] = d;
        ww[v] = w;
    }
    dfsz_and_eulerTour(1, -1);
    dfs (1, -1, 0, seg);
    cout << ans[1] << '\n';
    return 0;
} 



// int32_t main() {
//   ios_base::sync_with_stdio(0);
//   cin.tie(0);
//   // cin >> n;
//   int n = 5;
//   for (int i = 1; i <= n; i++) {
//     a[i] = i;
//   }
//   seg.build(1, 1, n); // building the segment tree
//   seg.upd(2, 10); // assiging 10 to the index 2 (a[2] := 10)
//   cout << seg.query(1, 5) << '\n'; // range max query on the segment [1, 5]

//   return 0;
// }

• Subtask 1: 0 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17