HDU - 6104 Influence 动态点分治

HDU - 6104

非常恶心的一道题， 维护的东西和幻想乡战略游戏差不多， 不过不同的是它的边权会变，

并且一个操作的贡献不会因为边权的改变而改变， 我们先考虑改变边权的时候不改变d1, d2数组，

那么在query进行u 和 fa[u]合并的时候， 那个边权会多加东西， 我们考虑改变边权的时候把多加的减掉就ok了， 

也就是多维护一个del 的 树状数组。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0);

using namespace std;

const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = (int)1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);

template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}
template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int LOG = 20;

int n, q;
vector<int> G[N];

int pa[N];
int w[N];
int depth[N];
int dfn[N];
int rmq_cnt;
int Log[N];
PII rmq[N][LOG];

int es[N];

struct Bit {
    int n;
    vector<int> a;
    void init(int _n) {
        n = _n;
        a.resize(n + 1);
        for(int i = 0; i <= n; i++) {
            a[i] = 0;
        }
    }
    inline void modify(int x, int v) {
        for(int i = x; i <= n; i += i & -i) {
            a[i] += v;
        }
    }
    inline int sum(int x) {
        int ans = 0;
        for(int i = x; i; i -= i & -i) {
            ans += a[i];
        }
        return ans;
    }
    inline int query(int L, int R) {
        if(L > R) return 0;
        return sum(R) - sum(L - 1);
    }
} bit, B[N], del[N];

void dfs(int u, int fa) {
    dfn[u] = ++rmq_cnt;
    rmq[rmq_cnt][0] = mk(depth[u], u);
    for(auto &v : G[u]) {
        if(v == fa) continue;
        bit.modify(rmq_cnt + 1, 1);
        es[v * 2] = rmq_cnt + 1;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        rmq[++rmq_cnt][0] = mk(depth[u], u);
        bit.modify(rmq_cnt + 1, -1);
        es[v * 2 + 1] = rmq_cnt + 1;
    }
}

void calcRmq() {
    for(int i = 2; i <= rmq_cnt; i++) {
        Log[i] = Log[i >> 1] + 1;
    }
    for(int j = 1; j <= Log[rmq_cnt]; j++) {
        for(int i = 1; i + (1 << j) - 1 <= rmq_cnt; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int getLca(int u, int v) {
    if(dfn[u] > dfn[v]) swap(u, v);
    int k = Log[dfn[v] - dfn[u] + 1];
    PII ret = min(rmq[dfn[u]][k], rmq[dfn[v] - (1 << k) + 1][k]);
    return ret.se;
}

int getDis(int u, int v) {
    int lca = getLca(u, v);
    return bit.sum(dfn[u]) + bit.sum(dfn[v]) - 2 * bit.sum(dfn[lca]);
}

int sz[N], mx[N], fa[N];
int center, now_tot;
bool ban[N];

void getSize(int u, int fa) {
    sz[u] = 1;
    for(auto &v : G[u]) {
        if(v == fa || ban[v]) continue;
        getSize(v, u);
        sz[u] += sz[v];
    }
}

void findCenter(int u, int fa) {
    mx[u] = 0;
    for(auto &v : G[u]) {
        if(v == fa || ban[v]) continue;
        findCenter(v, u);
        chkmax(mx[u], sz[v]);
    }
    chkmax(mx[u], now_tot - sz[u]);
    if(mx[center] > mx[u]) {
        center = u;
    }
}

int idx;
int dep[N];
int in[20][N], ot[20][N], fr[20][N];

LL sum[N], d1[N], d2[N];

void dfs(int u, int fa, int rt, int *in, int *ot, int *fr) {
    in[u] = ++idx;
    fr[u] = fa == rt ? u : fr[fa];
    for(auto &v : G[u]) {
        if(v == fa || ban[v]) continue;
        dfs(v, u, rt, in, ot, fr);
    }
    ot[u] = idx;
}

void divide(int u) {
    dfs(u, idx = 0, u, in[dep[u]], ot[dep[u]], fr[dep[u]]);
    B[u].init(idx);
    del[u].init(idx);
    ban[u] = true;
    for(auto &v : G[u]) {
        if(ban[v]) continue;

        getSize(v, 0);
        center = 0; now_tot = sz[v];
        findCenter(v, 0);
        fa[center] = u;
        dep[center] = dep[u] + 1;

        divide(center);
    }
}

void modifyEdge(int u, int v, int w) {
    int delVal = -w;
    bit.modify(es[v * 2], w);
    bit.modify(es[v * 2 + 1], -w);
    if(dep[u] > dep[v]) swap(u, v);
    for(int cur = u; cur; cur = fa[cur]) {
        int d = dep[cur];
        int pos = in[d][u] > in[d][v] ? u : v;
        int top = fr[d][pos];
        LL tmp = B[cur].query(1, in[d][top] - 1) + B[cur].query(ot[d][top] + 1, B[cur].n);
        del[cur].modify(in[d][pos], delVal * tmp);
        del[cur].modify(ot[d][pos] + 1, -delVal * tmp);
    }
}

void modifyPoint(int x, int w) {
    for(int cur = x; cur; cur = fa[cur]) {
        sum[cur] += w;
        B[cur].modify(in[dep[cur]][x], w);
        if(fa[cur]) {
            LL dis = 1LL * w * getDis(fa[cur], x);
            d2[cur] += dis;
            d1[fa[cur]] += dis;
        }
    }
}

inline LL query(int x) {
    LL ans = d1[x];
    for(int cur = x; fa[cur]; cur = fa[cur]) {
        ans += d1[fa[cur]];
        ans -= d2[cur];
        ans += (sum[fa[cur]] - sum[cur]) * getDis(x, fa[cur]);
        ans += del[fa[cur]].sum(in[dep[fa[cur]]][x]);
    }
    return ans;
}

void init() {
    rmq_cnt = 0;
    for(int i = 1; i <= n; i++) {
        G[i].clear();
        w[i] = 0;
        ban[i] = false;
        sum[i] = d1[i] = d2[i] = fa[i] = 0;
    }
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        init();
        for(int i = 2; i <= n; i++) {
            scanf("%d", &pa[i]);
            w[i] = 1;
            G[pa[i]].push_back(i);
            G[i].push_back(pa[i]);
        }

        bit.init(2 * n - 1);
        dfs(1, 0);
        calcRmq();


        mx[0] = inf;
        getSize(1, 0);
        center = 0; now_tot = sz[1];
        findCenter(1, 0);

        dep[center] = 1;
        divide(center);

        scanf("%d", &q);

        while(q--) {
            int op; scanf("%d", &op);
            if(op == 1) {
                int x; scanf("%d", &x);
                printf("%lld\n", query(x));
            }
            else if(op == 2) {
                int x, y;
                scanf("%d%d", &x, &y);
                modifyEdge(pa[x], x, y - w[x]);
                w[x] = y;
            }
            else {
                int x, y;
                scanf("%d%d", &x, &y);
                modifyPoint(x, y);
            }
        }
    }
    return 0;
}

/*
*/