#include<bits/stdc++.h>
using namespace std;
int n,u,v,d[1000005],l[1000005];
long long sum,s[1000005];
bool dfs(int idx,long long v){
    if(v*2==sum)
        return true;
    if(v*2>sum)
        return false;
    if(idx==n+1)
        return false;
    if(v+s[n]-s[idx]<sum/2)
        return false;
    bool lag=dfs(idx+1,v);
    if(lag){
        return true;
    }
    bool fag=dfs(idx+1,v+d[idx]);
    if(fag){
        l[idx]=1;
        return true;
    }
    return false;
}
int main(){
    cin>>n;
    d[1]=1;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        if(d[u])
            d[v]=d[u]+1;
        else
            d[u]=d[v]+1;
    }
    for(int i=1;i<=n;i++){
        sum+=d[i];
        s[i]=s[i-1]+d[i];
    }
    if(sum%2){
        cout<<-1;
        return 0;
    }
    if(!dfs(1,0)){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++){
        cout<<l[i]<<' ';
    }
    return 0;
}

本来WA的不多，全是TLE，然后脑抽写了个map想优化下，然后就是下面这个代码：

#include<bits/stdc++.h>
using namespace std;
int n,u,v,d[1000005],l[1000005];
long long sum,s[1000005];
map<long long,long long>f[1000005];
bool dfs(int idx,long long v){
    if(f[idx][v])
        return f[idx][v]-1;
    if(v*2==sum)
        return true;
    if(v*2>sum)
        return false;
    if(idx==n+1)
        return false;
    if(v+s[n]-s[idx]<sum/2)
        return false;
    bool lag=dfs(idx+1,v);
    if(lag){
        f[idx][v]=2;
        return true;
    }
    bool fag=dfs(idx+1,v+d[idx]);
    if(fag){
        l[idx]=1;
        f[idx][v]=2;
        return true;
    }
    f[idx][v]=1;
    return false;
}
int main(){
    cin>>n;
    d[1]=1;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        if(d[u])
            d[v]=d[u]+1;
        else
            d[u]=d[v]+1;
    }
    for(int i=1;i<=n;i++){
        sum+=d[i];
        s[i]=s[i-1]+d[i];
    }
    if(sum%2){
        cout<<-1;
        return 0;
    }
    if(!dfs(1,0)){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++){
        cout<<l[i]<<' ';
    }
    return 0;
}

然后虽然有些点不再TLE，但可以注意到有一些TLE的点在同一时刻MLE了，所以蒟蒻想问一下，该怎么优化最上面的第一份代码啊啊啊啊啊啊啊啊啊啊！

求调555