自动搬运

查看原文

来自洛谷，原作者为

	vector 拿不到 CF master 或高于 7 的等级别改个签

搬运于2025-08-24 23:17:15，当前版本为作者最后更新于2025-05-06 20:29:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

出题人题解。

特殊限制	做法或需要注意到的结论
$lim=0,n\le 10$	价值定义部分的操作不会在一个点重复执行。
$lim=0,n \le 20$	状压 DP 实现上面的结论。
$lim=0$	价值是所有边两端的数的异或和的总和。
$n\le 6$	断边操作不会执行。
$n \le 100$	价值是所有边两端数异或和的总和，断边操作不会执行。
无	同上面做法，上面那个是给树形 DP 写假了的。
$n \le 5 \times 10^4$	DP 是凸的，闵科夫斯基和。由于难度为黑，管理不建议放进比赛。

出题人做法

假设 $b(x,i)$ 表示非负整数 $x$ 的二进制表示中，从 $0$ 位算起，从低到高的第 $i$ 位的值。

假设 $lim=0$，即不存在对树的修改操作，也不存在附加代价的情况下，树的价值是多少。

显然，$s$ 必然等于 $all(i)$。

那么，先不考虑后面减去的那一项，答案会是什么样子。

此时，每操作一个节点 $u$，就相当于加上

$$\sum\limits_{0 \le i \le 63} \sum\limits_{v \in all(i) }[b(u,i) \gt b(v,i)]2^i $$

另外，每个节点最多被操作 $1$ 次，因为第二次操作不可能有贡献。

令 $dis(u,v)$ 表示 $u$ 点到 $v$ 点所需要经过的最少边数。

那么，所有的节点操作的贡献总和，似乎很像某个值？

一个我认为最容易想到的猜想： $\sum\limits_{dis(u,v)=1}(a_u \oplus a_v)$

然后，实际上上述操作（假设仍然忽略掉减少项）的总贡献并不是这个值。

原因是，一个数 $u$ 清零之后，原本如果一个位，使 $u$ 和它相邻的节点 $v$ 这一位都是 $1$，那么这一位原本不应该在任何时候产生贡献。

但是，操作了 $u$ 之后再操作 $v$，就导致这些位的贡献被错误地计算，因为 $u$ 的这一位的值被作为 $0$ 参与计算了。

这时候，再考虑题目式子中减去的那个值，发现刚好将这一项贡献减掉了。

所以猜想成立。

那么现在，如何考虑那两种对于树本身的修改呢？

对于第一种操作，考虑两个相邻点 $u,v$ ，如果不断开边，那么 $u,v$ 之间的贡献就是 $a_u \oplus a_v$，而断开边，需要多出 $a_u + a_v$ 的贡献，$a_u + a_v \ge a_u \oplus a_v$，这显然是不优的。

所以，第一种操作永远不会被执行。

对于第二种操作，考虑 dp。

树形 dp，令 $f_{u,i,0/1}$ 表示 $u$ 为根的子树执行了 $i$ 次删除操作，$u$ 自己被删或没被删，此时的最小总价值是多少。

审核管理做法

不观察到异或性质也可以通过本题，方法是设置边权，但是这种方法相对复杂。

加强版做法

我也不会，一个 7 级钩出题人显然是不会做黑题的。
但是既然做法存在，我就设置了 5 元的最优解奖金来征求 std。

std

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
typedef __int128 sll;
const int maxn=2005;
int n,lim;
sll a[maxn];
vi gp[maxn];
sll f[maxn][maxn][2];
// u/u exist/u.optimes : minimul xor sum
int siz[maxn];
void dfs(int u,int _fa){
    siz[u]=1;
    for(int& v:gp[u]){
        if(v==_fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
    sll g[2][maxn];
    {
        FOR(b,0,1){
            FOR(i,0,n)g[b][i]=1e30;
        }
        // u 存在
        g[0][0]=0;
        bool cur=0;
        int sz=0;
        for(int& v:gp[u]){
            if(v==_fa)continue;
            FOR(i,0,sz){
                FOR(j,0,siz[v]){
                    // v 存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][1]+(a[u]^a[v]));
                    // v 不存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][0]);
                }
            }
            FOR(i,0,sz)g[cur][i]=1e30;
            sz+=siz[v];
            cur^=1;
        }
        FOR(i,0,siz[u]){
            f[u][i][1]=g[cur][i];
        }
    }
    {
        FOR(b,0,1){
            FOR(i,0,n)g[b][i]=1e30;
        }
        // u 不存在
        g[0][1]=0;
        bool cur=0;
        int sz=1;
        for(int& v:gp[u]){
            if(v==_fa)continue;
            FOR(i,0,sz){
                FOR(j,0,siz[v]){
                    // v 存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][1]);
                    // v 不存在
                    ckmn(g[cur^1][i+j],g[cur][i]+f[v][j][0]);
                }
            }
            FOR(i,0,sz)g[cur][i]=1e30;
            sz+=siz[v];
            cur^=1;
        }
        FOR(i,1,siz[u]){
            f[u][i][0]=g[cur][i];
        }
    }
}
void solve(int id_of_test){
	read(n);
    read(lim);
    FOR(i,1,n){
        read(a[i]);
    }
    FOR(i,1,n-1){
        int u,v;
        read(u);
        read(v);
        gp[u].eb(v);
        gp[v].eb(u);
    }
    FOR(i,0,n){
        FOR(j,0,n){
            f[i][j][0]=f[i][j][1]=1e30;
        }
    }
    dfs(1,0);
    FOR(k,0,lim){
        sll ans=min(f[1][k][0],f[1][k][1]);
        wrint(ans);
        pc(' ');
    }
    pln
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

验题人 @LastKismet 的代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template<typename T> using vec=vector<T>;
template<typename T> using grheap=priority_queue<T>;
template<typename T> using lrheap=priority_queue<T,vector<T>,greater<T>>;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define file(f) freopen(#f".in","r",stdin);freopen(#f".out","w",stdout);

struct mint {
	int x,mod;
	inline mint(int o=0,int p=998244353) {x=o;mod=p;}
	inline mint & operator=(ll o){return x=o%mod,(x+=mod)>=mod&&(x-=mod),*this;}
	inline mint & operator+=(mint o){return (x+=o.x)>=mod&&(x-=mod),*this;}
	inline mint & operator-=(mint o){return (x-=o.x)<0&&(x+=mod),*this;}
	inline mint & operator*=(mint o){return x=(ll)x*o.x%mod,*this;}
	inline mint & operator^=(ll b){mint res(1);for(;b;b>>=1,*this*=*this)if(b&1)res*=*this;return x=res.x,*this;}
	inline mint & operator^=(mint o){return *this^=o.x;}
	inline mint & operator/=(mint o){return *this*=(o^=(mod-2));}
	inline mint & operator++(){return *this+=1;}
	inline mint & operator--(){return *this-=1;}
	inline mint operator++(int o){mint res=*this;return *this+=1,res;}
	inline mint operator--(int o){mint res=*this;return *this-=1,res;}
	friend inline mint operator+(mint a,mint b){return a+=b;}
	friend inline mint operator-(mint a,mint b){return a-=b;}
	friend inline mint operator*(mint a,mint b){return a*=b;}
	friend inline mint operator/(mint a,mint b){return a/=b;}
	friend inline mint operator^(mint a,ll b){return a^=b;}
	friend inline mint operator^(mint a,mint b){return a^=b;}
	friend inline bool operator<(mint a,mint b){return a.x<b.x;}
	friend inline bool operator>(mint a,mint b){return a.x>b.x;}
	friend inline bool operator<=(mint a,mint b){return a.x<=b.x;}
	friend inline bool operator>=(mint a,mint b){return a.x>=b.x;}
	friend inline bool operator==(mint a,mint b){return a.x==b.x;}
	friend inline istream & operator>>(istream &in,mint &o){ll x;return in>>x,o=x,in;}
	friend inline ostream & operator<<(ostream &ot,mint o){return ot<<o.x,ot;}
};

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=2005;

int n,lim;
i128 a[N];
vec<int> g[N];

int siz[N];
i128 f[N][N][2];

void dfs(int now,int fid){
	siz[now]=1;
	f[now][0][0]=f[now][1][1]=0;
	for(auto nxt:g[now]){
		if(nxt==fid)continue;
		dfs(nxt,now);
		per(i,siz[now],0)per(j,siz[nxt],0){
			if(j)chmin(f[now][i+j][0],f[now][i][0]+min(f[nxt][j][1],f[nxt][j][0]+(a[now]^a[nxt])));
else f[now][i+j][0]=f[now][i][0]+min(f[nxt][j][1],f[nxt][j][0]+(a[now]^a[nxt]));
			if(i)if(j)chmin(f[now][i+j][1],f[now][i][1]+min(f[nxt][j][0],f[nxt][j][1]));
            else f[now][i+j][1]=f[now][i][1]+min(f[nxt][j][0],f[nxt][j][1]);
		}
		siz[now]+=siz[nxt];
	}
}

void print(i128 x){
	if(x/10)print(x/10);
	cout<<char(x%10+'0');
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>lim;
	memset(f,0x3f,sizeof(f));
	rep(i,1,n){
		ll x;cin>>x;
		a[i]=x;
	}
	repl(i,1,n){
		int u,v;cin>>u>>v;
		g[u].pub(v);g[v].pub(u);
	}
	dfs(1,0);
	rep(i,0,lim)print(min(f[1][i][0],f[1][i][1])),cout<<' ';
	return 0;
}