SRM 692 Div 1 900

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

const ll m1 = 1e9;
const ll m2 = 1e6;
const int MAXN = 3e5+5;

#define A first
#define B second

ll n, ans[MAXN], sub[MAXN], totsub[MAXN];
vector<pii> g[MAXN];

// vertex v, tot = total so far, place = whether we have some vertex already walking along here
void dfs(int v, ll tot, ll place = -1, ll disttotop = 0) {
    //cout << v << ' ' << tot << ' ' << place << ' ' << disttotop << endl;
    ll ind = -1, tot1 = tot, dist1 = disttotop;
    for (pii u : g[v])
        if (2*sub[u.A] > sub[v])
            ind = u.A;
    if (place == -1)
        place = v;
    while (true) {
        bool y = false;
        for (pii u : g[place])
            if (2*sub[u.A] > sub[v]) {
                place = u.A; y = true;
                tot1 += u.B*(sub[v]-2*sub[u.A]);
                disttotop += u.B;
                break;
            }
        if (!y)
            break;
    }

    ans[v] = tot1;

    for (pii u : g[v]) {
        if (u.A != ind)
            dfs(u.A, totsub[u.A]);
        else {
            ll distofv = totsub[v]-(totsub[u.A]+u.B*sub[u.A]);
            tot1 -= distofv+disttotop*(sub[v]-sub[u.A]);
            dfs(u.A, tot1, place, disttotop-u.B);
        }
    }
}

void dfs1(ll v) {
    sub[v] = 1;
    for (pii u : g[v]) {
        dfs1(u.A);
        sub[v] += sub[u.A];
        totsub[v] += u.B*sub[u.A]+totsub[u.A];
    }
}

class TreeSums {
public:
    ll findSums(int N, int seed, int C, int D) {
        n = N;
        ll cur = seed;
        for (int i = 0; i <= N-2; ++i) {
            cur = (C*cur+D)%m1;
            ll pi = cur%(i+1);
            g[pi].push_back(pii(i+1, (C*cur+D)%m2));
            cur = (C*cur+D)%m1;
        }

        dfs1(0);
        dfs(0, totsub[0]);
        ll fin = 0;
        for (int i = 0; i < n; ++i) {
            fin ^= ans[i]; //cout << i << ' ' << ans[i] << endl;
        }
        return fin;
    }
};