Submission #1069150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069150		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	257 ms	76116 KiB

diameter

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define pipii pair<int, pair<int, int>>
#define vi vector<int>
#define vpi vector<pair<int, long long>>
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
const int N = 1e6 + 5;
using namespace std;
long long n, q, mod, tgian, in[N], out[N], pos[N], w[N];
vpi ad[N];
void dfs(int u, int p = 0)
{
    in[u] = ++tgian;
    for(auto [v, w] : ad[u])
    {
        if(v == p) continue ;
        pos[w] = v;
        dfs(v, u);
        ++tgian;
    }
    out[u]= tgian;
}

struct node
{
    long long du = 0, dw = 0, duw = 0, dwv = 0, duwv = 0;
    node operator + (const node &res) const
    {
        node tg ;
        tg.du = max(du, res.du);
        tg.dw = max(dw, res.dw);
        tg.duw = max(max(duw, res.duw), du + res.dw);
        tg.dwv = max(max(dwv, res.dwv), dw + res.du);
        tg.duwv = max(max(duwv, res.duwv), max(du + res.dwv, duw + res.du));
        return tg;
    }
};

long long lz[4*N*2];
node st[4*N*2];

void lazy(int id, int l, int r)
{
    if(lz[id] == 0) return ;
    long long v = lz[id];
    st[id].du += v;
    st[id].dw -= v + v;
    st[id].duw -= v;
    st[id].dwv -= v;
    if(l != r)
    {
        lz[2*id] += lz[id];
        lz[2*id+1] += lz[id];
    }
    lz[id] = 0;
}

void upd(int id, int l, int r, int u, int v, long long val)
{
    lazy(id, l, r);
    if(u > r or v < l) return ;
    if(u <= l and v >= r)
    {
        lz[id] += val;
        lazy(id, l, r);
        return ;
    }
    int mid = (l+r) / 2;
    upd(2*id, l, mid, u, v, val);
    upd(2*id+1, mid+1, r, u, v, val);
    st[id] = st[2*id] + st[2*id+1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    cin >> n >> q >> mod;
    for(int i = 1; i < n; ++i)
    {
        int u, v; long long c;
        cin >> u >> v >> c;
        ad[u].pb({v, i});
        ad[v].pb({u, i});
        w[i] = c;
    }

    dfs(1);

    for(int i = 1; i < n; ++i) upd(1, 1, tgian, in[pos[i]], out[pos[i]], w[i]);

    long long last = 0;

    while(q--)
    {
        int d; long long e;
        cin >> d >> e;
        d = 1 + (d + last) % (n-1); e = (e + last) % mod;
        upd(1, 1, tgian, in[pos[d]], out[pos[d]], e - w[d]);
        last = st[1].duwv, w[d] = e;
        cout << last << "\n";
    }
    return 0;
}

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