[BOJ 17642] Dynamic Diameter

https://www.acmicpc.net/problem/17642

 

센트로이드 분할과 레이지 세그를 이용한다면 이론적으로는 풀 수 있다. 하지만 그걸 언제 구현하고 앉았는가...

 

오일러 투어 순서를 나열해보자. 그리고 그 사이에 간선의 가중치를, 내려갈 때는 +, 올라갈 때는 -로 생각해보면..? 정점 $x$와 정점 $y$사이의 경로는 오일러 투어 상에서 $x$가 맨 처음 등장하는 위치를 $s_x$라 할 때 대략 $s_{x}$~$s_{y}$의 구간의 가중치를 적당히 더하고 뺀 값과 같게 된다. 정확히는, 구간을 두 개로 쪼개 앞쪽은 모두 빼고 뒤쪽은 모두 더한 결과의 최댓값과 같게 된다. 그 이유는, 우선 실제 경로상에 포함되지 않는 경로의 경우 내려갔다와 올라갔다와 모두 포함되기 때문에 상쇄되어 0이 되고, 경로상에서 올라가는 가중치는 모두 음수이고 내려가는 가중치는 모두 양수이기 때문이다.

 

다시 말해, 우리는 트리의 오일러 투어 순서에 따라 적당히 가중치를 매기고 어떤 연속한 구간에서 앞 쪽은 빼고 뒤 쪽은 더한 값의 최댓값을 구하는 쿼리로 구한다면 이 문제를 해결할 수 있다. 간선 가중치 업데이트 또한 두 개의 인덱스만 변경해주면 할 수 있다.

 

구간에서 앞 쪽은 빼고 뒤 쪽은 더하는 더한 값의 최대를 구할 때는, 금광을 풀 때처럼 세그먼트 트리의 노드를 정의하여 구할 수 있다. 총 7개의 변수가 필요한데, 왼쪽부터 더했을 때 최댓값, 오른쪽부터 뺐을 때 최댓값, 왼쪽부터 뺐다가 더했을 때의 최댓값, 오른쪽부터 더했다가 뺐을 때의 최댓값, 구간의 전체합, 전체 구간에서 앞 쪽을 빼고 뒤 쪽을 더할 때의 최댓값, 해당 구간에서의 답이 필요하다.

 

이 것들을 고려하면 임의의 두 구간을 하나로 합칠 수 있고, 이를 세그먼트 트리로 관리해주면 된다.

 

여담으로 대부분의 풀이가 나와 달랐다. lca인 점과 가장 깊은 점을 적당히 관리하고 어쩌구 하면 레이지 세그로 변수 5개만 정의하여 풀 수 있다고 한다.

 

코드

#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 9e18;

pair <pii, ll> Edge[MAX];
vector <pair <int, ll> > g[MAX];

class SegmentTree {
    struct Node {
        ll lmx = -LINF, rmn = -LINF, lc = -LINF, rc = -LINF, c = -LINF, s = 0, mx = -LINF;
        Node operator + (Node b) {
            Node ret;
            ret.lmx = max(lmx, s + b.lmx);
            ret.rmn = max(b.rmn, rmn - b.s);
            ret.lc = max({lc, b.lc - s, b.lmx + c});
            ret.rc = max({b.rc, rc + b.s, rmn + b.c});
            ret.c = max(c + b.s, b.c - s);
            ret.s = s + b.s;
            ret.mx = max({mx, b.mx, rmn + b.lc, rc + b.lmx});
            return ret;
        }
    };
    vector <Node> tree;
    int sz;
public: 
    SegmentTree() {}
    void Init(int n) {
        sz = n;
        tree.resize(4*n+10);
    }

    void update(int node, int s, int e, int k, ll val) {
        if(s == e) {
            tree[node].lmx = tree[node].s = val;
            tree[node].rmn = -val;
            tree[node].mx = tree[node].lc = tree[node].rc = tree[node].c = abs(val);
            return;
        }
        int m = s + e >> 1;
        if(k <= m) update(node<<1, s, m, k, val);
        else update(node<<1|1, m+1, e, k, val);
        tree[node] = tree[node<<1] + tree[node<<1|1];
    }

    void Update(int k, ll val) {
        update(1, 1, sz, k, val);
    }

    ll get() {
        return tree[1].mx;
    }
} ST;

int in[MAX], out[MAX], cnt;

void dfs(int x, int pa) {
    in[x] = out[x] = cnt++;
    for(auto i : g[x]) {
        if(i.fi == pa) continue;
        ST.Update(cnt, i.se);
        dfs(i.fi, x);
        out[x] = cnt++;
        ST.Update(out[x], -i.se);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, q; ll W;
    cin >> n >> q >> W;
    ST.Init(2*n-2);
    for(int i = 0; i < n - 1; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        g[u].eb(v, w);
        g[v].eb(u, w);
        Edge[i] = {{u, v}, w};
    }

    dfs(1, 0);
    ll ans = 0;
    while(q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + ans) % (n - 1);
        e = (e + ans) % W;
        int u = Edge[d].fi.fi, v = Edge[d].fi.se;
        if(in[u] < in[v]) swap(u, v);
        ST.Update(in[u], e);
        ST.Update(out[u]+1, -e);
        ans = ST.get();
        cout << ans << '\n';
    }
}