CF1120D Power Tree

首先这题有个非常显然的做法。考虑自深向浅放点，那么当决定在 $u$ 是否放点的时候子树内的叶子都被正好一个观察点覆盖或者只有一个没有被覆盖。否则是无法完成题目的条件的。所以我们可以 $dp[u][0/1]$ 表示 $u$ 子树内有 $0/1$ 个剩下的点做一次树形 dp。

可是还有一个更加优秀的做法。

我们考虑这个操作的本意其实是区间进行 + / - 。根据 NOIP 2018 的经验我们知道这个东西很多时候会转化成差分的 + 或者 - 。于是我们考虑把叶子提出来按照 dfs 序摆放。对于一次放东西操作，放下去后就是区间内可以同时增加一个值，也就是区间前面的差分加后面的差分减。我们可以连一条从区间开头到结尾后一个位置的边，表示可以同时操作这俩地方（一个加一个减）。

我们考虑连出来的图：

它有 $c + 1$ 个节点（其中 $c$ 为叶子数），因为可能连向最后一个叶子后一个节点。
这个图没有重边和自环（想一想发现显然）
因为想要选择最少的边，所以我们希望选边形成一棵树。为什么呢？差分的变换是不会让总大小和变化的。我们最终希望的是能够把所有权值都堆到最后一个叶子后面的那个虚点上，否则就得到的一定不是一个全 $0$ 的叶子序列。

于是选边的时候选出环来一定是不明智的，因为环上必然有一条边直到最后都不需要进行任何操作就可以完成把权值全部转移的目的（其他的点的权值向往外输的点通过一条链过去就好了），可以直接删掉这条边。

同时，如果不联通一定不可取。如果不联通了，必然有些点向最后一个叶子后面的那个虚点没有路，永远过不去，就爆炸了。

所以，最终选得到的一定就是这个图的最小生成树。

最后说一下输出答案。。这题不知道为啥要让你输出这种奇妙的东西，大概就是对每个权值分别判下哪些边可取再统一加入并查集就好了。。具体实现可以见代码。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n;
int A[MAXN] , deg[MAXN];
vi G[MAXN];

struct ed {
    int u , v , w , id;
} E[MAXN] ; int id;

int dfn[MAXN] , clo;
void dfs( int u , int fa ) {
    dfn[u] = clo + 1;
    if( u != 1 && deg[u] == 1 ) ++ clo;
    for( int v : G[u] ) if( v != fa ) dfs( v , u );
    E[++ id] = { dfn[u] , clo + 1 , A[u] , u };
}

bool cmp( ed u , ed v ) {
    return u.w < v.w;
}

int fa[MAXN];
int find( int x ) { return x == fa[x] ? x : fa[x] = find( fa[x] ); }

void solve() {
    cin >> n;
    rep( i , 1 , n ) scanf("%d",A + i);
    int u , v;
    rep( i , 2 , n ) scanf("%d%d",&u,&v) , G[u].pb( v ) , G[v].pb( u ) , ++ deg[u] , ++ deg[v];
    dfs( 1 , 1 );
    sort( E + 1 , E + 1 + n , cmp );
    rep( i , 1 , clo + 1 ) fa[i] = i;
    ll ans = 0;
    vi re;
    for( int i = 1 , j ; i <= n ; i = j ) {
        j = i;
        while( j != n + 1 && E[j].w == E[i].w ) {
            u = find( E[j].u ) , v = find( E[j].v );
            if( u != v ) re.pb( E[j].id );
            ++ j;
        }
        rep( k , i , j - 1 ) {
            u = find( E[k].u ) , v = find( E[k].v );
            if( u != v ) fa[u] = v , ans += E[k].w;
        }
    }
    cout << ans << ' ' << re.size() << endl;
    sort( all( re ) );
    for( int i : re ) printf("%d ",i);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}