题解：CF2127E Ancient Tree

· · 题解

直接猜测结论：只有根据初始条件被确定 cutie 的点最终是 cutie 的。

下面给出构造，先不考虑子树全空的点，最后往下传就行了。对于已经确定的点也无法改变了，下面讨论未确定的点。

随便选一种子树中已经确定的的颜色即可，该点不会被算。

选那一种即可，该点不会被算。

随便选一种子树中已经确定的的颜色即可，该点一定会被算。

一种好写的方式是启发式合并 set 维护子树中已经确定的颜色和在多个子树中出现的已经确定的颜色，时间复杂度 O(n\log ^2n)。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l),qwp=(r);i<=qwp;i++)
#define per(i,r,l) for(int i=(r),qwp=(l);i>=qwp;i--)
#define repll(i,l,r) for(ll i=(l),qwp=(r);i<=qwp;i++)
#define perll(i,r,l) for(ll i=(r),qwp=(l);i>=qwp;i--)
#define UQ(hsh,hc) (sort((hsh)+1,(hsh)+1+(hc)),(hc)=unique((hsh)+1,(hsh)+1+(hc))-(hsh)-1)
#define pb push_back
#define ins insert
#define clr clear
#define uset unordered_set
#define umap unordered_map
using namespace std;
namespace ax_by_c{
typedef long long ll;
const int N=2e5+5;
int n,k,w[N],a[N];
vector<int>g[N];
set<int>cs[N],cc;
ll ans;
void dfs(int u,int fa){
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    cc.clr();
    for(auto v:g[u]){
        if(v==fa)continue;
        if(cs[u].size()<cs[v].size())swap(cs[u],cs[v]);
        for(auto x:cs[v]){
            if(cs[u].count(x))cc.ins(x);
            else cs[u].ins(x);
        }
    }
    if((int)cc.size()>=2||((int)cc.size()==1&&a[u]&&a[u]!=*cc.begin()))ans+=w[u];
    if(a[u])cs[u].ins(a[u]);
    else{
        if(cc.size())a[u]=*cc.begin();
        else if(cs[u].size()) a[u]=*cs[u].begin();
    }
}
void dfs_(int u,int fa){
    if(!a[u])a[u]=a[fa];
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs_(v,u);
    }
}
void slv(int _csid,int _csi){
    scanf("%d %d",&n,&k);
    ans=0;
    rep(i,1,n){
        g[i].clr();
        cs[i].clr();
    }
    rep(i,1,n)scanf("%d",&w[i]);
    rep(i,1,n)scanf("%d",&a[i]);
    rep(i,1,n-1){
        int x,y;
        scanf("%d %d",&x,&y);
        g[x].pb(y),g[y].pb(x);
    }
    dfs(1,0);
    a[0]=1,dfs_(1,0);
    printf("%lld\n",ans);
    rep(i,1,n)printf("%d ",a[i]);putchar('\n');
}
void main(){
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1,csid=0;
    // scanf("%d",&csid);
    scanf("%d",&T);
    rep(i,1,T)slv(csid,i);
}
}
int main(){
    string __name="";
    if(__name!=""){
        freopen((__name+".in").c_str(),"r",stdin);
        freopen((__name+".out").c_str(),"w",stdout);
    }
    ax_by_c::main();
    return 0;
}
/*
g++ -std=c++14 -O2 -Wall -Wextra "-Wl,--stack=200000000" A.cpp -o A.exe
A.exe
*/