【BZOJ3727】PA2014 Final Zadanie 树形DP
2024-09-24 02:24:32
【BZOJ3727】PA2014 Final Zadanie
Description
吉丽YY了一道神题,题面是这样的:
“一棵n个点的树,每条边长度为1,第i个结点居住着a[i]个人。假设在i结点举行会议,所有人都从原住址沿着最短路径来到i结点,行走的总路程为b[i]。输出所有b[i]。”
吉丽已经造好了数据,但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗?
Input
第一行一个整数n(2<=n<=300000)。
接下来n-1行,每行两个整数x,y,表示x和y之间有连边。
接下来一行由空格隔开的n个整数b[i](0<=b[i]<=10^9)。
Output
输出一行由空格隔开的n个整数a[i]。
如果你觉得有多组解就任意输出其中一组。
Sample Input
2
1 2
17 31
1 2
17 31
Sample Output
31 17
题解:本题我们最好从反面入手,当我们知道a[i]求b[i]时,我们会这样搞:
设siz[i]表示i的子树内的总人数,tot表示总人数,所以当i!=1时,有
b[i]=b[fa[i]]+tot-2*siz[i]
//这个公式够朴素了吧~
移项
2*siz[i]-tot=b[fa[i]]-b[i]
观察这个式子,等号右面我们是可求的,于是我们把所有i=2...n这样的式子加起来,即
2*siz[2...n]-tot*(n-1)=b[fa[2...n]]-b[2..n]
我们思考siz[2...n]代表什么?不就是b[1]吗?//重点
然后我们就求出了tot,然后代入上面的式子求出siz[i],然后就能求出a[i]了
没谁了,这题我数据生成器的代码长度比我程序的长度都长~
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=300010;
int n,cnt;
int fa[maxn],to[maxn<<1],next[maxn<<1],head[maxn<<1],q[maxn];
long long siz[maxn],b[maxn],tot;
void dfs(int x)
{
q[++q[0]]=x;
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa[x]) fa[to[i]]=x,dfs(to[i]);
}
void add(int x,int y)
{
to[cnt]=y;
next[cnt]=head[x];
head[x]=cnt++;
}
int main()
{
scanf("%d",&n);
int i,x,y;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
for(i=1;i<=n;i++) scanf("%lld",&b[i]);
dfs(1);
for(i=2;i<=n;i++) tot+=b[fa[i]]-b[i];
tot=(2*b[1]-tot)/(long long)(n-1);
for(i=2;i<=n;i++) siz[i]=b[fa[i]]-b[i]+tot>>1;
siz[1]=tot;
for(i=2;i<=n;i++) siz[fa[q[i]]]-=siz[q[i]];
for(i=1;i<n;i++) printf("%lld ",siz[i]);
printf("%lld",siz[n]);
return 0;
}
最新文章
- 爬虫requests模块 2
- Repeater控件用法
- 【边框】-边框阴影-box-shadow
- mysql 在insert 时防止出现主键冲突错误的方法
- 引入的iframe是跨域的, 如何控制其高度
- ECMAScript 6 模块简介
- arduino电子琴(2015-11-04)
- Golang中的信号处理
- ejabberd为游戏免除注册限制
- linux.go
- TensorFlow之RNN:堆叠RNN、LSTM、GRU及双向LSTM
- Postman 安装及使用入门教程(我主要使用接口测试)
- java-js知识库之二——canvas绘制炫彩气泡
- python基本语法汇总
- 复杂sql查询语句
- MVC中常用的跳转方法
- Mysql更改表名大小写不敏感
- SQLite 剖析
- Delphi : Analyze PE file headers?
- C# FTP操作类可用