题意

树的结构不变,每个点有点权,每一条边有边权,有修改点权的操作,设x为树中一点.求\sum_idist(x,i)*a[i]的最小值

分析

我们把补给站叫做决策点,那么假设当前最优决策点为u.把u看作根节点,我们考虑将决策点从u转到儿子v,先假设sum[i]表示i子树内点权之和,那么减少的代价就是sum[v]*len(u,v),增多的代价就为(sum[u]-sum[v])*len(u,v)

所以说v比u优,当且仅当

也就是

不难发现,满足这个式子的儿子至多有一个.那么一个暴力的想法就是每次询问从根开始,往儿子下面走,如果不存在儿子比自己更优,那么自己就是决策点,否则就进入比自己优的儿子的子树.

这样每次询问的时间复杂度看似是O(n)的.但是实际上是O(Maxdepth)的.于是我们就有了想法,点分治不就是将深度减小为O(logn)了吗?我们把点分治中每一个重心的父亲设为上一层的重心,就在O(nlogn)的时间内构造了一棵点分树,这棵树的深度是O(logn)的,那么我们只需要在每个重心上维护子树信息,就可以在O(logn)的时间内求出把一个点当作决策点的答案,因为可以证明(但我不会)的是一对点在点分树中的lca一定存在于它们在原树上的路径,那么他们间的距离乘以点权只需要利用在lca上维护的子树信息来计算,具体方法就是一个点在点分树上往根节点跑,在路径上统计就能求出它作为决策点的答案(具体之后看代码).

我们将树的深度减小到了O(logn),所以每次查询只需要从根节点(整棵树的重心)开始,看哪一个(原树中)儿子更优,如果优就往儿子对应的子树的重心上走.每一次查询时间复杂度是O(20log^2n),一个log是要走的深度,一个log是求对应的答案,20是因为对于当前点u要计算所有儿子v作为决策点的值,题目中保证了一个点度数不超过20.而且因为是一旦搜到比自己优的儿子就去那一坨子树的重心,一般是跑不满20的.

再考虑修改,只用把自己在点分树中的祖先修改就行了,每一次时间复杂度O(logn)

实际上,每一次计算/修改都需要算两个点在原树上的距离,要求lca,可以用dfs序预处理+O(1)RMQ,从而整道题的时间复杂度为O(20nlog^2n),而我比较懒,求lca用的树剖,严格来说是O(20nlog^3n)的,但是树剖大多数时候达不到log,而且20也跑不满,那么就能过了...

修改/计算具体看代码

CODE

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<typename T>inline void read(T &num) {
    char ch; int flg = 1;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
    num*=flg;
}
const int MAXN = 100005;
int n, q, fir[MAXN], cnt;
struct edge { int to, nxt, w; }e[MAXN<<1];
inline void add(int u, int v, int wt) {
    e[cnt] = (edge){ v, fir[u], wt }, fir[u] = cnt++;
    e[cnt] = (edge){ u, fir[v], wt }, fir[v] = cnt++;
}
int dis[MAXN], son[MAXN], sz[MAXN], top[MAXN], fa[MAXN], dep[MAXN];
void dfs(int u, int ff) {
    dep[u] = dep[fa[u]=ff] + (sz[u]=1);
    for(int i = fir[u], v; ~i; i = e[i].nxt)
        if((v=e[i].to) != ff) {
            dis[v] = dis[u] + e[i].w;
            dfs(v, u), sz[u] += sz[v];
            if(sz[v] > sz[son[u]]) son[u] = v;
        }
}
void dfs2(int u, int tp) {
    top[u] = tp;
    if(son[u]) dfs2(son[u], tp);
    for(int i = fir[u], v; ~i; i = e[i].nxt)
        if((v=e[i].to) != fa[u] && v != son[u])
            dfs2(v, v);
}
int lca(int u, int v) { //
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v) { return dis[u] + dis[v] - 2*dis[lca(u,v)]; }
int Fa[MAXN], size[MAXN], Size, Minr, root, info[MAXN], CNT;
struct EDGE { int to, nxt, rt; }E[MAXN];
inline void ADD(int u, int v, int rr) {
    E[CNT] = (EDGE){ v, info[u], rr }, info[u] = CNT++;
}
bool vis[MAXN];

void Getrt(int u, int ff) {
    size[u] = 1;
    int ret = 0;
    for(int i = fir[u], v; ~i; i = e[i].nxt)
        if((v=e[i].to) != ff && !vis[v]) {
            Getrt(v, u), size[u] += size[v];
            ret = max(ret, size[v]);
        }
    ret = max(ret, Size-size[u]);
    if(ret < Minr) Minr = ret, root = u;
}
void DFS(int u, int ff) {
    vis[u] = 1; Fa[u] = ff;
    for(int i = fir[u], v; ~i; i = e[i].nxt)
        if(!vis[v=e[i].to]) {
            Minr = n; Size = size[v];
            Getrt(v, u);
            ADD(u, v, root);
            DFS(root, u);
        }
}

LL sum[MAXN]; //子树点数之和
LL sumd[MAXN]; //子树内的距离之和
LL sumf[MAXN]; //子树对父亲的贡献

inline void Modify(int u, int val) {
    sum[u] += val;
    for(int i = u; Fa[i]; i = Fa[i]) {
        int len = dist(u, Fa[i]);
        sum[Fa[i]] += val;
        sumd[Fa[i]] += 1ll * val * len;
        sumf[i] += 1ll * val * len;
    }
}

inline LL Count(int u) { //多理解一会,画画图多YY下
    LL res = sumd[u]; //自己子树的距离之和
    for(int i = u; Fa[i]; i = Fa[i]) {
        int len = dist(u, Fa[i]);
        res += (sum[Fa[i]]-sum[i]) * len; //Fa[i]的其他子树额外的点数 * 这一条边
        res += (sumd[Fa[i]]-sumf[i]); //Fa[i]的其他子树的点到Fa[i]的距离之和
        //上面两个统计都必须要减去这个子树的贡献,否则算重了
    }
    return res;
}
LL Query(int u) {
    LL tmp = Count(u);
    for(int i = info[u]; ~i; i = E[i].nxt)
        if(Count(E[i].to) < tmp) return Query(E[i].rt); //儿子比自己优就去对应的重心
    return tmp;
}
int main () {
    memset(fir, -1, sizeof fir);
    memset(info, -1, sizeof info);
    read(n), read(q);
    for(int i = 1, x, y, z; i < n; ++i)
        read(x), read(y), read(z), add(x, y, z);
    dfs(1, 0), dfs2(1, 1);
    Size = Minr = n; Getrt(1, 0); //先求一次重心
    int RT = root;                //作为根
    DFS(root, 0);
    int x, y;
    while(q--) {
        read(x), read(y);
        Modify(x, y);
        printf("%lld\n", Query(RT));
    }
}