[HNOI2014]米特运输

Description:

给你一棵树,每个点有权值,你可以修改一些点的权值使得:
1.每个点权值等于子节点权值的和
2.每个点的所有子节点权值相等

Hint:

\(n \le 2*10^6\)

Solution:

比较巧妙的题

首先有一个很显然的规律:

当一个点权值确定,整棵树就确定了 (为什么这么显然的规律没有想到)

然后我们考虑转化求对于每个点不改它,对应的树的形态

我们找出哪种树的形态\(i\)被计的最多,答案就是\(n-cnt_i\)

于是\(f[i]=a[i]*\prod_{j\in {anc_i} } son[j]\)

dfs之后sort一遍就行

但是这样会炸,要把乘换成加法\(-> log(x*y)=log(x)+log(y)\)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=2e6+5;
const double eps=1e-8;
int n,m,cnt,ans,a[mxn],son[mxn],hd[mxn];
double f[mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(int &x,int y) {if(xy) x=y;}

struct ed {
    int to,nxt;
}t[mxn<<1];

inline void add(int u,int v) {
    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

void dfs(int u,double sum) {
    f[u]=sum+log(a[u]);
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        dfs(v,sum+log(son[u]));
    }
}

int main()
{
    n=read(); int u,v;
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i
思维

相关

7个方法教你培养“成长型思维”

【人工智能导论：模型与算法】第六章 思维导图

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

codeforces和atcoder的思维题目

10张思维导图带你学习Java​Script

用象棋的思维趣说IT人的职业发展和钱途

思维&榜样

Redis 思维导图 (解析版)

程序设计思维与实践 Week3 作业 (3/4/数据班)

告别传统工业互联网，提高数字管控思维：三维组态分布式能源站

12月读书笔记3《程序员的思维训练》

《计算机思维》笔记

标签