Codeforces 1120 D Power Tree —— 最小生成树_codeforces 最小生成树

This way

题意：

给你一棵树，让你选择一些点，都有一个权值。每个点你可以对每个点做一次操作：将这个点所属子树的所有叶子结点加上一个值。问你如果想让所有的叶子结点取到任意值，取的点的权值和最小是多少，并且要输出所有可能可以取的点。

题解：

可以看出每个点都有一个管辖的区间，可以转换成为差分问题，然后的话可以将每个点的差分：l到r+1这两个点连条边（虽然我不是很懂为什么突然就可以转换到图上去）。这样的话将叶子结点取到任意值，也就是可以在每条边的一端加上一个值，在另一端减去一个值。这样要使得所有节点都能够修改到的话，这张差分图就必须要联通，那么又要所有的权值和最小，只需要找最小生成树即可。
对于第二个问题，查看每条边是否可以在最小生成树上，只需要每次对于相同权值的边，查看这两个端点是否属于同一集合即可，在这个权值查看完之后才能继续合并。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
struct node{
    int to,next;
}e[N*2];
int cnt,head[N],v[N];
void add(int x,int y){
    e[cnt].next=head[x];
    e[cnt].to=y;
    head[x]=cnt++;
}
struct edge{
    int x,y,val,id;
    bool operator< (const edge& a)const {
        return val<a.val;
    }
};
vector<edge>edg;
int tim,lef[N];
void dfs(int x,int fa){
    int f=0;
    for(int i=head[x];~i;i=e[i].next){
        int ne=e[i].to;
        if(ne==fa)continue;
        f=1;
        dfs(ne,x);
        lef[x]=lef[x]?lef[x]:lef[ne];
    }
    if(!f)
        tim++,lef[x]=tim;
    edg.push_back({lef[x],tim+1,v[x],x});
}
int fa[N];
int finds(int x){return x==fa[x]?fa[x]:fa[x]=finds(fa[x]);}
vector<int>ans;
int main()
{
    memset(head,-1,sizeof(head));
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]),fa[i]=i;
    fa[n+1]=n+1;
    for(int i=1;i<n;i++)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1,0);
    sort(edg.begin(),edg.end());
    ll sum=0;
    for(int i=0,j=0;i<edg.size();i=j){
        while(j<edg.size()&&edg[j].val==edg[i].val){
            int fax=finds(edg[j].x),fay=finds(edg[j].y);
            if(fax!=fay)
                ans.push_back(edg[j].id);
            j++;
        }
        for(int k=i;k<j;k++){
            int fax=finds(edg[k].x),fay=finds(edg[k].y);
            if(fax!=fay)
                sum+=(ll)edg[k].val,fa[fay]=fax;
        }
    }
    printf("%lld %d\n",sum,ans.size());
    sort(ans.begin(),ans.end());
    for(auto i:ans)
        printf("%d ",i);
    printf("\n");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71