Submission #1256838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256838		the_rizzler	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	159 ms	31536 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
using node = array<ll, 3>;
const int N = 2e5 + 10;
int n, q;
ll v;
vector<node>a[N];
struct TopTree {
    int cnt, rt, siz[N], son[N], pos[N], ppos[N], fa[N];
    struct Data {
        int sz;
        ll f[2][2];//上界点/下界点
        inline ll *operator[](int x) {
            return f[x];
        }
        inline friend Data operator*(Data A, Data B) { //Compess A<-B
            Data C;
            C.sz = A.sz + B.sz;
            C[0][0] = max({A[0][0], B[0][0], A[0][1] + B[1][0]});
            C[0][1] = max(B[0][1], A[0][1] + B[1][1]);
            C[1][0] = max(A[1][0], A[1][1] + B[1][0]);
            C[1][1] = A[1][1] + B[1][1];
            return C;
        }
        inline friend Data operator+(Data A, Data B) { //Rake A<-B
            Data C;
            C.sz = A.sz + B.sz;
            C[0][0] = max({A[0][0], B[0][0], A[1][0] + max(B[1][0], B[1][1])});
            C[0][1] = max(A[0][1], A[1][1] + max(B[1][0], B[1][1]));
            C[1][0] = max({A[1][0], B[1][0], B[1][1]});
            C[1][1] = A[1][1];
            return C;
        }
    };
#define ls tr[rt].lson
#define rs tr[rt].rson
    struct node {
        int fa, lson, rson, op;
        Data v;
    } tr[N];
    inline void pushup(int rt) {
        if (tr[rt].op == 1)
            tr[rt].v = tr[ls].v * tr[rs].v;

        if (tr[rt].op == 2)
            tr[rt].v = tr[ls].v + tr[rs].v;
    }
    inline Data newdata(ll w) {
        Data A;
        A.sz = 1;
        A[0][0] = A[1][0] = A[1][0] = A[1][1] = w;
        return A;
    }
    inline int newnode(ll w) {
        int rt = ++cnt;
        tr[rt].v = newdata(w), tr[rt].op = 0;
        ls = rs = tr[rt].fa = 0;
        return rt;
    }
    inline int newnode(int lp, int rp, int op) {
        int rt = ++cnt;
        tr[rt].op = op, ls = lp, rs = rp;
        tr[lp].fa = tr[rp].fa = rt;
        return pushup(rt), rt;
    }
    inline void dfs0(int x) {
        siz[x] = 1;

        for (auto tp : a[x]) {
            int t = tp[0], id = tp[2];
            ll w = tp[1];

            if (t == fa[x])
                continue;

            ppos[id] = pos[t] = newnode(w);
            fa[t] = x, dfs0(t), siz[x] += siz[t];

            if (siz[t] > siz[son[x]])
                son[x] = t;
        }
    }
    vector<int>pc;
    inline int build(int l, int r, int op) {
        if (l == r)
            return pc[l];

        int mid = r - 1, sz = 0;

        for (int i = l; i <= r; i++)
            sz += tr[pc[i]].v.sz;

        for (int i = l, s = 0; i < r; i++) {
            s += tr[pc[i]].v.sz;

            if (s * 2 >= sz) {
                mid = i;
                break;
            }
        }

        return newnode(build(l, mid, op), build(mid + 1, r, op), op);
    }
    inline int dfs(int x) {
        vector<int>vc;

        if (pos[x])
            vc.push_back(pos[x]);

        for (int p = x; son[p]; p = son[p]) {
            vector<int>vp;

            for (auto tp : a[p]) {
                int t = tp[0];

                if (t == son[p] || t == fa[p])
                    continue;

                vp.push_back(dfs(t));
            }

            if (!vp.size())
                vc.push_back(pos[son[p]]);
            else
                pc = vp, vc.push_back(newnode(pos[son[p]], build(0, vp.size() - 1, 2), 2));
        }

        pc = vc;
        int rtp = build(0, vc.size() - 1, 1);
        return rtp;
    }
    inline void init() {
        dfs0(1), rt = dfs(1);
    }
    inline void modify(int x, ll w) {
        tr[ppos[x]].v = newdata(w);

        for (int p = tr[ppos[x]].fa; p; p = tr[p].fa)
            pushup(p);
    }
    inline ll query() {
        return max({tr[rt].v[0][0], tr[rt].v[0][1], tr[rt].v[1][0], tr[rt].v[1][1]});
    }
} T;
ll las;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q >> v;
  

    for (int i = 1; i < n; i++) {
        int u,v;
        ll w;
        cin >> u >> v >> w;
        a[u].push_back((node) {
            v, w, i
        });
        a[v].push_back((node) {
            u, w, i
        });
    }

    T.init();

    while (q--) {
      int x;
      ll w;
      cin >> x >> w;
      
      x = (x + las) % (n - 1) + 1;
      w = (w + las) % v;
      T.modify(x, w);
      cout << (las = T.query()) << "\n";
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27