【2022省选模拟】树点购买——结论，树形DP

此题不提供链接 题目描述

题解

通过一点观察和推理发现，最优解相当于是把这棵树做了一个树链剖分（不是重链也不是长链，是任意链的剖分，但是要保证链底是叶子），然后每条链上选一个权值最小的节点。

于是我们可以设 f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1] 表示对 i i i 的子树进行树链剖分（0表示 i i i 所在的链还没选点，1表示已经选了点）的最小权值和，按照定义转移即可。

注意 f [ i ] [ 1 ] f[i][1] f[i][1] 可以先不考虑选点 i i i，最后再一步从 f [ i ] [ 0 ] f[i][0] f[i][0] 转移过来。

这样就可以解决问题1了。

问题3只需要在DP的同时记录一下即可。

问题2的话，可以考虑把DP转移状态图建出来，最后进行一次遍历即可。

具体来说，我们每一步DP需要新建一个节点代表这个DP状态，然后考虑这个DP值是从哪些状态转移过来的，我们就把边连向那些状态对应的节点。

举个例子：在按顺序枚举 u u u 的儿子节点 v v v 的过程中， f [ v ] [ 0 ] + f [ u ] [ 1 ] ≤ f [ u ] [ 0 ] f[v][0]+f[u][1] \le f[u][0] f[v][0]+f[u][1]≤f[u][0] 需要转移，用 a a a 表示 f [ u ] [ 0 ] f[u][0] f[u][0] 原来的节点， a ′ a' a′ 表示 f [ u ] [ 0 ] f[u][0] f[u][0] 新建的节点， b , c b,c b,c 表示 f [ u ] [ 1 ] f[u][1] f[u][1] 和 f [ v ] [ 0 ] f[v][0] f[v][0] 的节点，那么你需要连边 a ′ → b , a ′ → c a'\rightarrow b,a'\rightarrow c a′→b,a′→c，如果 f [ v ] [ 0 ] + f [ u ] [ 1 ] = f [ u ] [ 0 ] f[v][0]+f[u][1] = f[u][0] f[v][0]+f[u][1]=f[u][0]，那么原来的状态也可以是最优解，需要连边 a ′ → a a'\rightarrow a a′→a。

总复杂度 O ( n ) O(n) O(n)。

注意建图的点数至少需要开六倍，六倍！

代码

具体过程可以看看代码

#include//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('\n')
using namespace std;
const int MAXN=2000006;
const ll INF=1e17;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
inline void print(ll x,char c='\n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
inline ll lowbit(ll x){return x&-x;}

#define pll pair<ll,ll>
#define fi first
#define se second
const ll MOD=998244353;
struct edge{
	int v,to;edge(){}
	edge(int V,int T){v=V,to=T;}
}e[MAXN<<3];
int EN,G[MAXN],D[MAXN<<2];
inline void addedge(int u,int v){
	e[++EN]=edge(v,G[u]),G[u]=EN;
	e[++EN]=edge(u,G[v]),G[v]=EN;
}
inline void addedge_(int u,int v){
	e[++EN]=edge(v,D[u]),D[u]=EN;
}
int n,IN,id[MAXN][2],op;
ll c[MAXN];
pll f[MAXN][2];
bool vis[MAXN<<2];
inline pll merg(const pll&a,const pll&b){
	return pll(a.fi+b.fi,a.se*b.se%MOD);
}
inline void dfs(int x,int fa){
	f[x][0]=pll(0,1),id[x][0]=++IN;
	f[x][1]=pll(0,1),id[x][1]=++IN;
	for(int i=G[x];i;i=e[i].to){
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,x);
		IN++,addedge_(IN,id[x][0]),id[x][0]=IN;
		f[x][0]=merg(f[x][0],f[v][1]);
		addedge_(id[x][0],id[v][1]);
		
		if(f[v][0].fi+f[x][1].fi<=f[x][0].fi){
			ll ad=0;
			if(f[v][0].fi+f[x][1].fi==f[x][0].fi)
				addedge_(IN+1,id[x][0]),ad=f[x][0].se;
			id[x][0]=++IN;
			f[x][0]=merg(f[v][0],f[x][1]),(f[x][0].se+=ad)%=MOD;
			addedge_(id[x][0],id[v][0]);
			addedge_(id[x][0],id[x][1]);
		}
		
		IN++,addedge_(IN,id[x][1]),id[x][1]=IN;
		f[x][1]=merg(f[x][1],f[v][1]);
		addedge_(id[x][1],id[v][1]);
	}
	if(f[x][1].fi==0)f[x][1].fi=INF;
	if(f[x][0].fi+c[x]<=f[x][1].fi){
		ll ad=0;
		if(f[x][0].fi+c[x]==f[x][1].fi)
			addedge_(IN+1,id[x][1]),ad=f[x][1].se;
		id[x][1]=++IN;
		f[x][1]=merg(f[x][0],pll(c[x],1)),(f[x][1].se+=ad)%=MOD;
		addedge_(id[x][1],id[x][0]);
		addedge_(id[x][1],x);
	}
}
signed main()
{
	freopen("purtree.in","r",stdin);
	freopen("purtree.out","w",stdout);
	n=read(),IN=n;
	for(int i=1;i<=n;i++)c[i]=read();
	for(int i=1;i<n;i++)addedge(read(),read());
	dfs(1,0);
	op=read();
	int root=id[1][1];
	queue<int>q;
	q.push(root),vis[root]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=D[u];i;i=e[i].to){
			int v=e[i].v;
			if(!vis[v])vis[v]=1,q.push(v);
		}
	}
	print(f[1][1].fi);
	if(op>1){
		for(int i=1;i<=n;i++)if(vis[i])print(i,' ');
		END;
	}
	if(op>2)print(f[1][1].se);
	return 0;
}
/*
啥逼pdf样例都复制不起
5
500 100 300 200 100
1 2
2 3
2 4
1 5
3

3
100 100 100
1 2
1 3
3
*/