bzoj 3727: Final Zadanie 思维题

题目:

Description

吉丽YY了一道神题，题面是这样的：

“一棵n个点的树，每条边长度为1，第i个结点居住着a[i]个人。假设在i结点举行会议，所有人都从原住址沿着最短路径来到i结点，行走的总路程为b[i]。输出所有b[i]。”

吉丽已经造好了数据，但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗？

题解:

对于节点\(u\)设其父亲为\(fa_u\).子树的\(a_i\)之和为\(sum_i\)

设\(SUM = \sum_{u \in G}a_u\)

则对于任意的\(u \neq 1\)有:\(b_u - b_{fa_u} = SUM - 2*sum_u\)

且\(b_1 = \sum_{u \neq 1}sum_u\)

然后我们将所有的\(b_u - b_{fa_u} = SUM - 2*sum_u\)求和

得:\(\sum (b_u - b_{fa_u}) = (n-1)*SUM - 2\sum_{u \neq 1}sum_u\)

我们将\(b_1 = \sum_{u \neq 1}sum_u\)翻倍加上去有.

\(2*b_1 = \sum (b_u - b_{fa_u}) = (n-1)*SUM\)

于是我们有:\(SUM = \frac{2*b_1 + \sum_{u \neq 1}(b_u - b_{fa_u})}{n-1}\)

既然我们得到了SUM,那么将其代入到所有的\(b_u - b_{fa_u} = SUM - 2*sum_u\)中即可

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 300010;

int n;

struct Egde{

	int to,next;

}G[maxn<<1];

int head[maxn],cnt;

void add(int u,int v){

	G[++cnt].to = v;

	G[cnt].next = head[u];

	head[u] = cnt;

}

int b[maxn],sum[maxn],fa[maxn],a[maxn];

#define v G[i].to

void dfs1(int u){

	for(int i = head[u];i;i=G[i].next){

		if(v == fa[u]) continue;

		fa[v] = u;dfs1(v);

	}

}

void dfs2(int u){

	a[u] = sum[u];

	for(int i = head[u];i;i=G[i].next){

		if(v == fa[u]) continue;

		dfs2(v);a[u] -= sum[v];

	}

}

#undef v

inline void init(){

	memset(head,0,sizeof head);

	cnt = 0;

}

int main(){

	init();read(n);

	for(int i=1,u,v;i<n;++i){

		read(u);read(v);

		add(u,v);add(v,u);

	}

	memset(sum,0,sizeof sum);

	memset(fa,0,sizeof fa);

	for(int i=1;i<=n;++i) read(b[i]);

	dfs1(1);

	ll x = 0;

	for(int i=2;i<=n;++i){

		x += b[i] - b[fa[i]];

	}x += 2LL*b[1];

	ll SUM = x/(n-1);

	sum[1] = SUM;

	for(int i=2;i<=n;++i){

		sum[i] = SUM - (b[i] - b[fa[i]]);

		sum[i] >>= 1;

	}

	dfs2(1);

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

		printf("%d",a[i]);

		if(i != n) putchar(' ');

		else putchar('\n');

	}

	return 0;

}

巴特西

bzoj 3727: Final Zadanie 思维题

题目:

题解:

最新文章

热门文章