CF1187E Tree Painting

洛咕

分析:换根\(dp\)的模板题了.先假设\(1\)号点为根,求出\(f[u]\)表示以点\(u\)为根的子树产生的贡献.现在考虑换根的式子,手玩一棵树就行了.

#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,size[N];ll ans,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 dfs1(int u,int fa){
	size[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		dfs1(v,u);size[u]+=size[v];
	}
}
inline void dp(int u,int fa){
	f[u]=size[u];
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		dp(v,u);f[u]+=f[v];
	}
}
inline void dfs2(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]-size[v]+n-size[v];
		ans=max(ans,f[v]);dfs2(v,u);
	}
}
int main(){
	n=read();
	for(int i=1;i
动态规划-树形DP

相关

标签