题解 P3345 【[ZJOI2015]幻想乡战略游戏】
Ark_
2019-03-20 16:20:03
# 题意
树的结构不变,每个点有点权,每一条边有边权,有修改点权的操作,设$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$优,当且仅当
$sum[v]*len(u,v)>(sum[u]-sum[v])*len(u,v)$
也就是
$2*sum[v]>sum[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
```cpp
#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));
}
}
```