CF1092F Tree with Maximum Cost

洛咕

伪双倍经验,这题是边权,但是做法一样

题意:\(n\)个节点的树，每个节点有点权\(a_i\).定义\(dist(x,y)\)为\(x\)到\(y\)的边数.选取一个点\(v\),使得\(\sum_{i=1}^ndist(i,v)*a_i\)最大.

分析:选取的那个点\(v\)不就是树的根?相当于要以每个点为根求一次贡献,然后取\(max?\)那不就是换根\(dp?\)转移手玩一下就行了.

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2e5+5;
int n,a[N];ll ans,cost[N],f[N];
int tot,head[N],nxt[N<<1],to[N<<1];
inline void add(int a,int b){
	nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void pre_dfs(int u,int fa){
	cost[u]=a[u];
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		pre_dfs(v,u);cost[u]+=cost[v];
	}
}
inline void dfs(int u,int fa){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		dfs(v,u);f[u]+=f[v]+cost[v];
	}
}
inline void dp(int u,int fa){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		f[v]=f[u]-cost[v]+cost[1]-cost[v];
		ans=max(ans,f[v]);dp(v,u);
	}
}
int main(){
	n=read();for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i
动态规划-树形DP

相关

标签