【题解】BZOJ 3924 幻想乡战略游戏

请注意,本文编写于 173 天前,最后修改于 135 天前,其中某些信息可能已经过时。

Problem

给定一棵带权树,有 $m$ 个操作,每次可修改某个点的权值,对于每个操作,输出带权距离和最小值

Thought

每个点的答案就是 $\sum_{i=1}^{n}dis(x,i)*u[i]$
因为在树上动态做这样的东西,自然而然想到动态点分治

如果原图中某个儿子节点的总距离小于当前节点,那么带权重心在这个儿子节点方向,那么只需要递归查询点分树上哪个儿子节点包含了该节点

考虑如何维护总距离
先记录个总权值 $sumkey$
对于点分树上的点,我们记录下这些东西:

  1. 点分树子树中权值和 $sumKey[x]$
  2. 点分树子树中到重心的带权距离和 $sumDis[x]$
  3. 点分树子树中到重心的父亲节点的带权距离和 $sumDisFa[x]$

显然,点分树上根节点 $rt$ 的答案就是其子树到它的带权距离和
对于某个儿子节点,子树部分的贡献就是子树到它的带权距离和 $sumDis[x]$,而非子树部分为 $sumKey[fa]$ 去掉这个儿子对他的贡献 $sumkey[x]$ 再乘上这次移动距离的贡献 $dis(x,fa)$

所以说查询任意节点答案的复杂度为 $\log n$

所以说从点分树根节点开始查询,每次在原树的每个儿子处试探查询,若使得答案变小,递归查询点分树上子树即可

时间复杂度 $O(m\log^2 n)$

ps:此题玄学调参对时间复杂度影响很大,所以能过就行...

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
typedef long long ll;
struct edge {
    int t , n , w;
    void add(int _t , int _n , int _w) {t = _t; n = _n; w = _w;}
}e[N << 1] , E[N];
int head[N] , headE[N] , tot , totE;

int siz[N] , max_siz[N] , root , pre[N];
ll sumkey , sumKey[N] , sumDis[N] , sumDisFa[N];

int f[N << 1][22] , dep[N] , fst[N] , DFN;
int bintwo[22] , logtwo[N << 1];

bool vis[N];
int n , m;
ll ans[N];

void addedge(int , int , int);
void addEdge(int , int , int);
//***
//ST
//***
void dfs(int , int);
void prepare();
int lca(int , int);
ll dis(int , int);
//***
//dfs
//***
void getSize(int , int);
void getRoot(int , int , int);
void getDisFa(int , int , int);
void build(int);

void change(int , ll);
ll query(int);
ll cal(int);

int main() {
    n = read(); m = read();
    for(int i = 1 ; i < n ; ++ i) {
        int u = read() , v = read() , w = read();
        addedge(u , v , w); addedge(v , u , w);
    }

    getSize(1 , 0);
    getRoot(1 , 0 , siz[1]);
    int rt = root;
    build(rt);

    dfs(1 , 1);
    prepare();
    while(m --) {
        int u = read() , v = read();
        sumkey += v;
        change(u , v);
        printf("%lld\n" , query(rt));
    }
    return 0;
}
void addedge(int u , int v , int w) {
    e[++ tot].add(v , head[u] , w);
    head[u] = tot;
}
void addEdge(int u , int v , int w) {
    E[++ totE].add(v , headE[u] , w);
    headE[u] = totE;
}
void dfs(int x , int deep) {
    fst[x] = ++ DFN; dep[x] = deep;
    f[DFN][0] = x;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(fst[e[i].t]) continue;
        dfs(e[i].t , deep + e[i].w);
        f[++ DFN][0] = x;
    }
}
void prepare() {
    bintwo[0] = 1;
    for(int i = 1 ; i <= 20 ; ++ i)
        bintwo[i] = bintwo[i - 1] << 1;
    logtwo[0] = - 1;
    for(int i = 1 ; i <= 200000 ; ++ i)
        logtwo[i] = logtwo[i / 2] + 1;
    for(int j = 1 ; j <= logtwo[n << 1] ; ++ j)
        for(int i = 1 ; i + bintwo[j] - 1 <= (n << 1) ; ++ i)
            f[i][j] = dep[f[i][j - 1]] < dep[f[i + bintwo[j - 1]][j - 1]] ? f[i][j - 1] : f[i + bintwo[j - 1]][j - 1];
}
int lca(int u , int v) {
    u = fst[u]; v = fst[v];
    if(u > v) swap(u , v);
    int len = logtwo[v - u + 1];
    return dep[f[u][len]] < dep[f[v - bintwo[len] + 1][len]] ? f[u][len] : f[v - bintwo[len] + 1][len];
}
ll dis(int u , int v) {return dep[u] + dep[v] - 2 * dep[lca(u , v)];}
void getSize(int x , int fa) {
    siz[x] = 1;
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t]) {
            getSize(e[i].t , x);
            siz[x] += siz[e[i].t];
        }
}
void getRoot(int x , int fa , int sum_siz) {
    max_siz[x] = 0;
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t]) {
            getRoot(e[i].t , x , sum_siz);
            max_siz[x] = max(max_siz[x] , siz[e[i].t]);
        }
    max_siz[x] = max(max_siz[x] , sum_siz - siz[x]);
    if(!root || max_siz[x] < max_siz[root]) root = x;
}
void build(int x) {
    vis[x] = 1;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(vis[e[i].t]) continue;
        root = 0;
        getSize(e[i].t , x);
        getRoot(e[i].t , x , siz[e[i].t]);
        
        int rt = root;
        addEdge(x , rt , e[i].t);
        pre[rt] = x;
        build(rt);
    }
    vis[x] = 0;
}
void change(int x , ll p) {
    sumKey[x] += p;
    for(int i = x ; pre[i] ; i = pre[i]) {
        sumKey[pre[i]] += p;
        sumDisFa[i] += p * dis(x , pre[i]);
        sumDis[pre[i]] += p * dis(x , pre[i]);
    }
}
ll query(int x) {
    ll sumx = cal(x);
    for(int i = headE[x] ; i ; i = E[i].n) {
        ll sumson = cal(E[i].w);
        if(sumson < sumx)
            return query(E[i].t);
    }
    return sumx;
}
ll cal(int x) {
    ll ans = sumDis[x];
    for(int i = x ; pre[i] ; i = pre[i]) {
        ans += sumDis[pre[i]] - sumDisFa[i];
        ans += (sumKey[pre[i]] - sumKey[i]) * dis(x , pre[i]);
    }
    return ans;
}
Comments

添加新评论