题解：P12895 [POI 2019/2020 R2] 假期 Wakacje Bajtazara

sunkuangzheng · 2025-06-21 13:40:17 · 题解

容易发现将树黑白染色后，可以游览的城市颜色相同，因此首先枚举黑白，将另一种颜色点权全部设置为 0。

分析我们能走的点的形态，不难发现其实是“毛毛虫”状物，即一条链和到这条链距离为 1 的点。

求解最大权毛毛虫是经典套路，首先记一个点 u 相邻所有点权值和（包括自己）为 f_u，则一条路径的 f_u 全部相加后，链中间每个点算了 3 次，端点算了两次。因此记 g_u = f_u - 2a_u，路径权值即为 a_u + a_v + \sum f_x，类似树的直径求解 DP 即可（注意这里有负权点，可能无法使用两遍 dfs），注意需要钦定直径两端的颜色是我们选择的。

最后输出方案是简单的，按顺序遍历直径输出旁边的点即可。复杂度线性。

/**
 *    author: sunkuangzheng
 *    created: 21.06.2025 14:37:44
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 1e6+5;
using namespace std;
int T,n,a[N],u,v,c[N],w[N],fa[N]; vector<int> g[N]; ll f[N];
pair<ll,int> dp[N]; ll W; int du,dv;
void dfs1(int u,int f){
    c[u] = c[f] ^ 1,fa[u] = f;
    for(int v : g[u]) if(v != f) dfs1(v,u);
}void dfs2(int u){
    if(w[u]) dp[u] = {w[u] + f[u],u}; else dp[u] = {-1e18,0}; 
    for(int v : g[u]) if(v != fa[u]){
        dfs2(v);
        if(dp[u].first + dp[v].first > W)
            W = dp[u].first + dp[v].first,
            du = dp[u].second,dv = dp[v].second;
        dp[u] = max(dp[u],{dp[v].first + f[u],dp[v].second}); 
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
    if(n <= 2){
        cout << *max_element(a+1,a+n+1) << "\n";
        cout << "1\n";
        cout << max_element(a+1,a+n+1) - a << "\n";
        return 0;
    }dfs1(1,0);
    for(int co : {0,1}){
        for(int i = 1;i <= n;i ++) w[i] = (c[i] == co) * a[i];
        for(int i = 1;i <= n;i ++){
            f[i] = -w[i];
            for(int j : g[i]) f[i] += w[j]; 
        }dfs2(1);
        // debug(W,du,dv);
        // printarr(1,n,f);
    }dfs1(du,0);
    vector<int> p;
    cout << W << "\n";
    while(dv) p.push_back(dv),dv = fa[dv];
    // if(p.size() % 2 == 0) p.pop_back();
    assert(p.size() & 1); 
    vector<int> as;
    for(int i = 0;i < p.size();i ++){
        as.push_back(p[i]);
        if(!(i & 1)) continue;
        else{
            for(int v : g[p[i]]) if(v != p[i-1] && v != p[i+1])
                as.push_back(v),as.push_back(p[i]);
        }
    }//if(as.size() % 2 == 0) as.pop_back();
    assert(as.size() % 2 == 1);
    cout << (as.size() + 1) / 2 << "\n";
    for(int v : as) cout << v << " ";
    cout << "\n";
}