雅礼培训4.3 Problem A 【点分治】

题目简述

一个\(N\)个节点的树，有\(M\)个炸弹分布在一些节点上，有各自的威力，随着其他点距离增大对其他点的伤害呈等差减小，直至为0

问每个点受到的伤害

题解

QAQ考场代码没处理好有些炸弹威力很大这个事实，，数组爆掉。。。

AC算法直接变暴力分，，，

点分治即可

我是每次将子树内所有的炸弹统计到根来，再用一个差分数组求出各个深度受到的伤害，累加入每个节点的答案

但是由于可能会出现伤害来自同一个子树的情况，我们再对每个子树做一遍撤销

常数略大，，经玄学优化强行卡入时限

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

using namespace std;

const int maxn = 500005,maxm = 600005,INF = 100000000;

inline int read(){

	int out = 0; char c = getchar();

	while (c < 48 || c > 57) c = getchar();

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out;

}

inline void write(LL x){

	LL tmp = 0; int cnt = 0;

	while (x) tmp = (tmp << 3) + (tmp << 1) + x % 10,x /= 10,cnt++;

	while (cnt--) putchar(tmp % 10 + 48),tmp /= 10;

	putchar('\n');

}

int h[maxn],ne = 2,n,m;

struct EDGE{int to,nxt;}ed[maxn * 2];

int F[maxn],Siz[maxn],rt,sum,vis[maxn];

int siz[maxn],st[maxm],top,d[maxn],fa[maxn],nd[maxn],ndi;

int md;

LL ans[maxn],D[maxn];

vector<int> power[maxn];

inline void build(int u,int v){

	ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;

	ed[ne] = (EDGE){u,h[v]}; h[v] = ne++;

}

void getRT(int u){

	Siz[u] = 1 + power[u].size();

	F[u] = 0;

	Redge(u) if (!vis[to = ed[k].to] && to != fa[u]){

		fa[to] = u;

		getRT(to);

		Siz[u] += Siz[to];

		F[u] = max(F[u],Siz[to]);

	}

	F[u] = max(F[u],sum - Siz[u]);

	if (F[u] < F[rt]) rt = u;

}

void dfs1(int u){

	Siz[u] = 1 + power[u].size(); siz[u] = 1;

	nd[++ndi] = u;

	md = max(md,d[u]);

	Redge(u) if (!vis[to = ed[k].to] && to != fa[u]){

		fa[to] = u; d[to] = d[u] + 1;

		dfs1(to);

		Siz[u] += Siz[to];

		siz[u] += siz[to];

	}

}

void dfs4(int u){

	nd[++ndi] = u;

	for (int j = 0; j < power[u].size(); j++){

		if (power[u][j] > d[u] + 1) st[++top] = power[u][j] - d[u] - 1;

	}

	Redge(u) if (!vis[to = ed[k].to] && to != fa[u]){

		dfs4(to);

	}

}

void dfs5(int u){

	ans[u] -= D[d[u]];

	Redge(u) if (!vis[to = ed[k].to] && to != fa[u]){

		dfs5(to);

	}

}

void cal(int u){

	top = 0;

	for (int j = 0; j < power[u].size(); j++)

		if (power[u][j] > 2) st[++top] = power[u][j] - 2;

	for (int i = 0; i <= siz[u]; i++) D[i] = 0;

	ndi = 0;

	Redge(u) if (!vis[to = ed[k].to] && to != fa[u]){

		dfs4(to);

	}

	for (int i = 1; i <= top; i++){

		if (st[i] <= md){

			D[1] += st[i];

			D[2] += -1 - st[i];

			D[st[i] + 2] += 1;

		}

		else {

			D[1] += st[i];

			D[2] += -1 - st[i];

		}

	}

	for (int i = 1; i <= siz[u]; i++) D[i] += D[i - 1];

	for (int i = 1; i <= siz[u]; i++) D[i] += D[i - 1];

	ans[u] -= D[1];

	for (int i = 1; i <= ndi; i++) ans[nd[i]] -= D[d[nd[i]]];

}

void solve(int u){

	vis[u] = true; siz[u] = 1; Siz[u] = 1 + power[u].size();

	ndi = 0; md = 0;

	Redge(u) if (!vis[to = ed[k].to]){

		fa[to] = u; d[to] = 1;

		dfs1(to);

		siz[u] += siz[to];

		Siz[u] += Siz[to];

	}

	md += 2;

	if (Siz[u] == siz[u]) return;

	top = 0;

	for (int j = 0; j < power[u].size(); j++) st[++top] = power[u][j];

	for (int i = 1; i <= ndi; i++){

		int v = nd[i];

		for (int j = 0; j < power[v].size(); j++){

			if (power[v][j] > d[v]) st[++top] = power[v][j] - d[v];

		}

	}

	for (int i = 0; i <= siz[u]; i++) D[i] = 0;

	for (int i = 1; i <= top; i++){

		if (st[i] <= md){

			D[0] += st[i];

			D[1] += -1 - st[i];

			D[st[i] + 1] += 1;

		}

		else {

			D[0] += st[i];

			D[1] += -1 - st[i];

		}

	}

	for (int i = 1; i <= siz[u]; i++) D[i] += D[i - 1];

	for (int i = 1; i <= siz[u]; i++) D[i] += D[i - 1];

	ans[u] += D[0];

	for (int i = 1; i <= ndi; i++) ans[nd[i]] += D[d[nd[i]]];

	Redge(u) if (!vis[to = ed[k].to]){

		if (siz[to] == Siz[to]) continue;

		cal(to);

	}

	Redge(u) if (!vis[to = ed[k].to]){

		if (siz[to] == Siz[to]) continue;

		sum = Siz[to]; F[rt = 0] = INF;

		getRT(to);

		solve(rt);

	}

}

int main(){

	//double t = clock();

	//freopen("1.in","r",stdin);

	//freopen("a.out","w",stdout);

	n = read(); m = read();

	int pos,w;

	for (int i = 2; i <= n; i++) build(i,read());

	for (int i = 1; i <= m; i++){

		pos = read(); w = read();

		power[pos].push_back(w);

	}

	F[rt = 0] = INF; sum = n + m;

	getRT(1);

	solve(rt);

	for (int i = 1; i <= n; i++) write(ans[i]);

	//cerr << (clock() - t) / CLOCKS_PER_SEC << 's' << endl;

	return 0;

}

巴特西

雅礼培训4.3 Problem A 【点分治】

题目简述

题解

最新文章

热门文章