LibreOJ 2135 「ZJOI2015」幻想乡战略游戏

发表于 | 分类于 | 5

果然点分治这种东西跑不过树剖啊（

首先，有一个结论：最优的补给站的位置就是树的重心，不过原来的子树大小要换成子树点权和。
证明：假设最优解是一个在重心以外的点 x，令其向重心移动一步。设走过的这条边边权为 w，会走到 y。
那么会发现在 y 那边的点的贡献全部少了 w，在 x 这边的点的贡献全部多了 w。
由于 x 不是重心，所以 y 那边的点权和一定大于 x 这边的点权和。
故越接近重心解就更优，最优解即重心。

求重心比较简单，根据重心的性质，其实重心就是满足 2sizex≥sizeroot 的最深的 x。其中 root 表示树根。
在线段树上根据 DFS 序维护 size，然后直接线段树上二分找最深的即可。
用 DFS 序是因为 DFS 序越大就越深（当然是同一条链上）。

设重心为 u，那么问题就变成了求 n∑v=1dv⋅dist(u,v)。
这个其实也挺套路的，首先把路径转化为到根相减，然后分别写成三个和式，得 n∑v=1dv⋅dist(root,u)+n∑v=1dv⋅dist(root,v)−2n∑v=1dv⋅dist(root,lca(u,v))

前两个和式很方便维护，重点在于第三个。
考虑 u 到根路径上的一个点 x 到其一个儿子 y 的一条边权为 w 的边，显然它会影响 y 子树内的所有点的贡献，即 w⋅sizey。因为这些点和 u 的 lca 到根的路径必然会经过这条边。
于是令 wp 表示 p 到其父亲的边权，最后一个和式其实就是对 u 到根路径上的每一个点 x，求出 sizex⋅wx 之和。

修改时需要改动 size，实际上改动的就是该点到根的路径上的 size。
线段树和树剖维护即可。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <algorithm>
#include <utility>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 1e5;
int n,q;
int to[(N << 1) + 5],val[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v,int w)
{
    static int tot = 0;
    to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],rk[N + 5];
int w[N + 5];
long long dis[N + 5];
long long sum_d,sum_d_dis;
void dfs1(int p)
{
    sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dis[to[i]] = dis[p] + val[i],w[to[i]] = val[i],dfs1(to[i]),sz[p] += sz[to[i]];
            if(!son[p] || sz[son[p]] < sz[to[i]])
                son[p] = to[i];
        }
}
void dfs2(int p)
{
    static int tot = 0;
    rk[id[p] = ++tot] = p;
    if(son[p])
        top[son[p]] = top[p],dfs2(son[p]);
    for(register int i = first[p];i;i = pre[i])
        if(!id[to[i]])
            top[to[i]] = to[i],dfs2(to[i]);
}
struct node
{
    int sz,add;
    long long sum,w;
} seg[(N << 2) + 10];
void build(int p,int tl,int tr)
{
    if(tl == tr)
    {
        seg[p].w = w[rk[tl]];
        return ;
    }
    int mid = tl + tr >> 1;
    build(ls,tl,mid),build(rs,mid + 1,tr);
    seg[p].w = seg[ls].w + seg[rs].w;
}
void update(int l,int r,int k,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        seg[p].sz += k,seg[p].add += k,seg[p].sum += seg[p].w * k;
        return ;
    }
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,ls,tl,mid),1);
    r > mid && (update(l,r,k,rs,mid + 1,tr),1);
    seg[p].sz = max(seg[ls].sz,seg[rs].sz) + seg[p].add;
    seg[p].sum = seg[ls].sum + seg[rs].sum + seg[p].w * seg[p].add;
}
pair<long long,long long> operator+(pair<long long,long long> a,pair<long long,long long> b)
{
    return make_pair(a.first + b.first,a.second + b.second);
}
pair<long long,long long> query(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return make_pair(seg[p].sum,seg[p].w);
    pair<long long,long long> ret = make_pair(0,0);
    int mid = tl + tr >> 1;
    l <= mid && (ret = ret + query(l,r,ls,tl,mid),1);
    r > mid && (ret = ret + query(l,r,rs,mid + 1,tr),1);
    ret.first += ret.second * seg[p].add;
    return ret;
}
int query(int add,int p,int tl,int tr)
{
    if(tl == tr)
        return rk[tl];
    int mid = tl + tr >> 1;
    if((seg[rs].sz + add + seg[p].add) * 2 >= seg[1].sz)
        return query(add + seg[p].add,rs,mid + 1,tr);
    else
        return query(add + seg[p].add,ls,tl,mid);
}
void update(int x,int k)
{
    for(;x;x = fa[top[x]])
        update(id[top[x]],id[x],k,1,1,n);
}
long long query(int x)
{
    long long ret = 0;
    for(;x;x = fa[top[x]])
        ret += query(id[top[x]],id[x],1,1,n).first;
    return ret;
}
int main()
{
    scanf("%d%d",&n,&q);
    int u,v,w;
    for(register int i = 1;i < n;++i)
        scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
    dep[1] = top[1] = 1,dfs1(1),dfs2(1),build(1,1,n);
    int x,k;
    for(;q;--q)
    {
        scanf("%d%d",&x,&k);
        sum_d += k,sum_d_dis += dis[x] * k,update(x,k);
        int p = query(0,1,1,n);
        printf("%lld\n",sum_d_dis + sum_d * dis[p] - 2 * query(p));
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment