CF1120 D. Power Tree 巧妙的图论转化
[前题提要]:无
题目描述:
就是给你一棵树,然后每个点有花费,然后你可以选一个点,付费后对这个点的子树的所有叶子结点增减任意权值.
考虑有一个人会给这棵树的所有叶子结点赋值(值我们不知道),输出最小的花费,使得无论它如何赋值,我们使用上述的花
费都能使所有的叶子节点变为0
考虑对一个点的子树的所有叶子节点进行增减任意值.不难联想到对一个点的子树的所有节点增减任意值的做法.所以考虑使用类似于树链剖分的方式将树上修改化为链上区间修改.
考虑记录一个点的所有叶子节点,并且按照
d
f
s
dfs
dfs序将其离散化存下.按照
d
f
s
dfs
dfs序的性质,我们会发现一个点的所有叶子节点必然是连续的区间.那么此时我们的问题就变成了:
给你
n
n
n个可以修改的区间,每一个区间都有其修改范围,修改每一个区间需要一定花费,问你至少需要多少花费将所有数字变为0
考虑到区间修改以及单点查询,我们想到使用差分来解决.假设我们使用一个差分数组
k
[
i
]
=
a
[
i
]
−
a
[
i
−
1
]
k[i]=a[i]-a[i-1]
k[i]=a[i]−a[i−1],那么对于每一次区间修改来说,我们都是
a
[
l
]
+
=
v
a
l
,
a
[
r
+
1
]
−
=
v
a
l
a[l]+=val,a[r+1]-=val
a[l]+=val,a[r+1]−=val,那么最终我们需要得到的所有的
k
[
i
]
=
=
0
k[i]==0
k[i]==0.
此时有一个巧妙的转化,考虑我们需要所有的k[i]变为0,但是显然我们的差分数组是不改变前缀和的,所以此时所有的值肯定都转移到了cnt+1的位置(假设我们有cnt个叶子节点),那么对于我们的数的转移来说,我们只能将
l
l
l转移到
r
+
1
r+1
r+1,如果我们将转移过程看成边,将每一个叶子结点看成点,那么我们想将所有的值都转移到
c
n
t
+
1
cnt+1
cnt+1,就需要所有的点都联通才行,这样才能保证无论怎么赋值我们都可以将其转移到
c
n
t
+
1
cnt+1
cnt+1的位置
那么此时这道题就简单了,考虑到必须所有点都联通,每次选择联通一个点我们都需要花费,又需要花费最小,所以显然是个最小生成树的模型,此时使用最小生成树跑一下就行.
但是还有一个问题,那就是这道题的最终问题是所有的可能性的最小生成树的点,所以我们用朴素的
k
r
u
s
k
a
l
kruskal
kruskal跑出来的只是一棵树,需要改一下.考虑到最小生成树的性质,当边相同时,我们可以选择任意一条不在联通块中的边,所以这些边显然都是平等的,所以这些边都是我们的答案(当然这一点是可以严谨证明的,但是限于篇幅,此处不再赘述)
下面是具体的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int w[maxn];vector<int>edge[maxn];int l[maxn],r[maxn];
int cnt=0;
void dfs(int u,int per_u) {
if(edge[u].size()==1&&u!=1) {
++cnt;l[u]=r[u]=cnt;
}
for(auto v:edge[u]) {
if(v==per_u) continue;
dfs(v,u);
l[u]=min(l[u],l[v]);
r[u]=max(r[u],r[v]);
}
}
struct Edge{
int u,v,w,id;
bool operator < (const Edge &rhs) const {
return w<rhs.w;
}
}edge2[maxn];
int fa[maxn];
int find(int x) {
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
signed main() {
int n=read();
for(int i=1;i<=n;i++) {
w[i]=read();
}
for(int i=1;i<n;i++) {
int u=read();int v=read();
edge[u].push_back(v);
edge[v].push_back(u);
}
memset(l,0x3f,sizeof l);
memset(r,-0x3f,sizeof r);
dfs(1,0);
for(int i=1;i<=n;i++) {
int u=l[i],v=r[i];
edge2[i]={u,v+1,w[i],i};
}
for(int i=1;i<=cnt;i++) fa[i]=i;
sort(edge2+1,edge2+1+n);
vector<int>ans;int this_cnt=0;int need=0;
for(int i=1;i<=n;i++) {
int r=i;
while(r+1<=n&&edge2[r+1].w==edge2[r].w) r++;
for(int j=i;j<=r;j++) {
auto [u,v,w,k]=edge2[j];
if(find(u)!=find(v)) {
this_cnt++;ans.push_back(k);
}
}
for(int j=i;j<=r;j++) {
auto [u,v,w,k]=edge2[j];
if(find(u)!=find(v)) {
need+=w;
fa[find(u)]=find(v);
}
}
i=r;
}
sort(ans.begin(),ans.end());
cout<<need<<" "<<ans.size()<<endl;
for(auto i:ans) cout<<i<<" ";
return 0;
}