题意

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

分析

我们把补给站叫做决策点,那么假设当前最优决策点为uuu.把uuu看作根节点,我们考虑将决策点从uuu转到儿子vvv,先假设sum[i]sum[i]sum[i]表示iii子树内点权之和,那么减少的代价就是sum[v]∗len(u,v)sum[v]*len(u,v)sum[v]∗len(u,v),增多的代价就为(sum[u]−sum[v])∗len(u,v)(sum[u]-sum[v])*len(u,v)(sum[u]−sum[v])∗len(u,v).所以说vvv比uuu优,当且仅当sum[v]∗len(u,v)>(sum[u]−sum[v])∗len(u,v)sum[v]*len(u,v)>(sum[u]-sum[v])*len(u,v)sum[v]∗len(u,v)>(sum[u]−sum[v])∗len(u,v)也就是2∗sum[v]>sum[u]2*sum[v]>sum[u]2∗sum[v]>sum[u]不难发现,满足这个式子的儿子至多有一个.那么一个暴力的想法就是每次询问从根开始,往儿子下面走,如果不存在儿子比自己更优,那么自己就是决策点,否则就进入比自己优的儿子的子树.

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

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

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

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

其实这就是个暴力…优雅的暴力…

修改/计算具体看代码

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; int totsize = Size;

	for(int i = fir[u], v; ~i; i = e[i].nxt)

		if(!vis[v=e[i].to]) {

			Minr = n;

			Size = size[v] > size[u] ? totsize - size[u] : size[v];

			//此处不能直接用size[v],因为那是以1为根求出来的size

			//这里问号语句判断size大小是在看u和v在1为根的树中谁是谁的儿子

			//从而可以计算出以u为根时v的子树大小,自己YY一下...

			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]); //注意这里是到u的距离

		sum[Fa[i]] += val; //累加点数

		sumd[Fa[i]] += 1ll * val * len; //累加距离之和

		sumf[i] += 1ll * val * len; //累加i这个子树对i父亲的贡献(记在i上)

	}

}

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]); //注意这里是到u的距离

		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));

	}

}

巴特西

BZOJ 3924 / Luogu P3345 [ZJOI2015]幻想乡战略游戏 (动态点分治/点分树)

题意

分析

CODE

最新文章

热门文章