Submission #938919

#	Time	Username	Problem	Language	Result	Execution time	Memory
938919		vjudge1	Magic Tree (CEOI19_magictree)	C++17	14 / 100	193 ms	25052 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 n, m, k;
struct ST {
  int t[4 * N];
  static const int inf = 1e9;
  ST() {
    memset(t, 0, sizeof t);
  }
  void upd(int _n, int b, int e, int i, int 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, n, idx, x);
  }

  int 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
  }
  int query(int l, int r) {
    return query (1, 1, n, l, r);
  }
};
///

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);
        }
    }
    seg.upd(dd[u], seg.query(0, 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);
        } 
    }

    seg.upd(dd[u], seg.query (0, dd[u]) + ww[u]);
    ans[u] = max(ans[u], 1LL * seg.query (0, 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]]--;
            seg.upd(dd[cc], 0);
        }
    }
}

int32_t main () {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int nn;
    cin >> nn >> m >> k;
    n = k;
    ST seg;
    for (int i = 2; i <= nn; i++) {
        int p; cin >> p;
        adj[p].push_back(i);
    }   

    for (int i = 1; i <= m; 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;
} 

• 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