CF1120D Power Tree——一题多解
https://www.luogu.com.cn/problem/CF1120D
给你一棵树，想象你可以对于每个点 \(x\)，用 \(c_x\) 的花费得到子树中所有叶子的权值和，你想要解出所有叶子的权值，最少要多少花费？（相较于原题，题意有改动，是根据模拟赛的题意来的）\(n\le 10^6,1\le c_x\le 10^9\)
法1.区间转差分的思想+最小生成树
你可以把叶子按从左到右（直观的）看成一个序列，每个点可以对序列的一个可知的区间进行区间查和这样的（想象），运用区间转差分的思想，\([l,r]\) 可以换成 \(\lang l,r+1\rang\)，在一个大小为 \(cnt\_leaf+1\) 的图里将 \(l,r+1\) 连一条权值为 \(c_x\) 的边；只需要最后叶子们都连通，根据 \(n\) 元一次方程组需要 \(n\) 个方程解出，则转化为最小生成树问题。
难点在于第二问，对于最小生成树的边数组（已排序）连续的一段一样的边权的边，合法的都可能，而处理完这一段得到的图的连通性都是一样的，所以不会影响后续。具体不太好说，看代码吧。
#include
using namespace std;
const int N=1e6+5;
int n,dfc,id_lf,c[N],u[N],v[N],fa[N],lf[N],rf[N],dfn[N],num[N];
vectorG[N];
struct J{int u,v,w,id;}e[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){fa[find(y)]=find(x);}
void dfs1(int x,int p){
bool is_lf=1;
for(int i=0;ist;
long long sum=0;
for(int i=1;i<=n;i++){
int j=i-1;
while(j 法2.DP
也可以用树形dp做，但我还没有调出来，因为我的写法很折腾人。这个做法远远不如法1来得优美，但没办法，你看下面这个plus问题
第三问：最优方案有几种？两种方案不同当且仅当取的 \(x\) 的集合不同。
如果沿用最小生成树的方法，将可以以连续相同的一段为子问题形成一些求生成树个数的问题，即矩阵树定理解决，复杂度很高，弃用。而这里使用树dp就会很方便。
设 \(f[i][0/1]\) 表示以 \(i\) 为根的子树中的所有叶子只剩 \(0/1\) 个没有被解出来需要的最小花费，\(g[i][0/1]\) 表示对应方案数。
依次枚举子节点并递归，那么每个时刻最开始 \(f,g\) 都代表前...个子节点的子树中的所有叶子...的对应值：
f[x][0]=f[x][1]=0,g[x][0]=g[x][1]=1;
for(int i=0;imycode
#include //Power Tree+: 三个问
using namespace std;
const int N=1e6+5,mod=998244353;
int n,dfc,id_lf,c[N],u[N],v[N],fa[N],lf[N],rf[N],dfn[N],num[N],g[N][2];
long long f[N][2];
vectorG[N];
struct J{int u,v,w,id;}e[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){fa[find(y)]=find(x);}
void dfs1(int x,int p){
bool is_lf=1;
for(int i=0;if[x][1]+c[x])f[x][0]=f[x][1]+c[x],g[x][0]=g[x][1];
else if(f[x][0]==f[x][1]+c[x])g[x][0]=(g[x][0]+g[x][1])%mod;
}
void print(int x){
if(x/10)print(x/10);
putchar(x%10+48);
}
int main(){
freopen("purtree.in","r",stdin);freopen("purtree.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;ist;
long long sum=0;
for(int i=1;i<=n;i++){
int j=i-1;
while(j>cs;
sort(st.begin(),st.end());
if(cs>=2)for(int i=0;i=3)dfs(1,0),print(g[1][0]);
}