Description
给定一棵有根树,可以用的代价控制点,控制后可以给该点子树里的叶子同时加上一个数。求最小代价,使得叶子上为任何不同的数,你都可以把它们变为。
Solution
首先将叶子结点按照序排序,为一个序列。
控制一个点后加上一个数的操作相当于区间加,可以考虑在差分数组上操作。
将所有叶子结点变为,相当于将差分数组变为。若对应区间,那么可以修改序列上和的值。将所有值都变为,需要可以修改的位置连接起来,即形成一棵树。于是将每个店的建一条边,跑一边最小生成树即可。
Code
- #include<cstdio>
- #include<vector>
- #include<algorithm>
- #define pb push_back
- #define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
- #define per(i, a, b) for (register int i=(a); i>=(b); --i)
- using namespace std;
- inline void chkmax(int &x, int y){x<y?(x=y):0;}
- inline void chkmin(int &x, int y){x>y?(x=y):0;}
- const int N=200005;
- struct node{int x, y, w, id;}E[N];
- bool operator < (node a, node b){return a.w<b.w;}
- int L[N], R[N], deg[N], fa[N], ans[N], val[N], sum, cnt;
- vector<int> G[N];
- long long res;
-
- inline int read()
- {
- int x=0,f=1;char ch=getchar();
- for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
- for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
- return x*f;
- }
-
- void dfs(int u, int fa)
- {
- if (deg[u]==1 && u>1) L[u]=R[u]=++cnt;
- for (int v: G[u]) if (v^fa)
- {
- dfs(v, u);
- chkmin(L[u], L[v]);
- chkmax(R[u], R[v]);
- }
- E[u]=(node){L[u], R[u]+1, val[u], u};
- }
-
- int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
-
- int main()
- {
- int n=read();
- rep(i, 1, n) val[i]=read(), L[i]=n;
- rep(i, 1, n-1)
- {
- int u=read(), v=read();
- G[u].pb(v); G[v].pb(u);
- deg[u]++; deg[v]++;
- }
- dfs(1, 0);
- sort(E+1, E+n+1);
- rep(i, 1, cnt+1) fa[i]=i;
- for (int l=1, r=1; l<=n; l=r+1, r++)
- {
- while (E[r].w==E[r+1].w && r<n) r++;
- rep(i, l, r)
- {
- int fx=find(E[i].x), fy=find(E[i].y);
- if (fx^fy) sum++, ans[E[i].id]=1;
- }
- rep(i, l, r)
- {
- int fx=find(E[i].x), fy=find(E[i].y);
- if (fx^fy) fa[fx]=fy, res+=(long long)E[i].w;
- }
- }
- printf("%lld %d\n", res, sum);
- rep(i, 1, n) if (ans[i]) printf("%d ", i);
- return 0;
- }