妙啊算错时间复杂度了
题目大意：给你一棵$n$个节点的二叉树，每个节点要么是叶子节点，要么拥有恰好两个儿子。
令$m$为叶子节点个数，你需要在这棵二叉树中选择$i$个叶子节点染色，叶节点染色需要一定的代价，非叶子节点代价为两孩子的染色节点数量的异或和乘上一常数。请最小化代价。
数据范围：$n≤4000$。
显然这是一道$dp$题。
令$f[u][i]$表示在以$u$号点为根的子树中，选择$i$个叶子节点染色的最小代价。
若u为叶子节点，不难得出$f[u][0]=0$，$f[u][1]=c[u]$。
我们不难得出$f[u][i+j]=min{f[lc][i]+f[rc][j]+c[u]*(i\ xor\ j)}$，其中$lc$，$rc$表示$u$的左儿子和右儿子，$c[u]$表示$u$号节点的常数。
然后这个$dp$转移，看似是$O(n^3)$的，实际上：
$T(n)=2T(\frac{n}{2})+O(n^2)$。这个实际上还是$O(n^2)$的。。。。。。。。
然后就愉快地做完了，注意卡常。
#include<bits/stdc++.h>
#define M 4005
#define L long long
#define INF (1<<28)
using namespace std;
int l[M]={},r[M]={},siz[M]={},c[M]={},vis[M]={},f[M][M]={}; void dfs(int x){
if(vis[x]) return; vis[x]=;
if(l[x]==&&r[x]==){
siz[x]=;
f[x][]=; f[x][]=c[x];
return;
}
dfs(l[x]); dfs(r[x]);
siz[x]=siz[l[x]]+siz[r[x]];
for(int i=;i<=siz[l[x]];i++){
for(int j=;j<=siz[r[x]];j++)
f[x][i+j]=min(f[x][i+j],f[l[x]][i]+f[r[x]][j]+c[x]*(i^j));
}
} int Main(){
memset(vis,,sizeof(vis));
int n; scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d",l+i,r+i);
for(int i=;i<=n;i++) scanf("%d",c+i);
for(int i=;i<=n;i++) memset(f[i],,(n+)<<);
for(int i=;i<=n;i++) dfs(i);
int rt=; for(int i=;i<=n;i++) if(siz[rt]<siz[i]) rt=i;
for(int i=;i<=siz[rt];i++)
printf("%d ",f[rt][i]);
printf("\n");
}
int main(){
int cas; cin>>cas;
while(cas--) Main();
}