题解：P3549 [POI2013] MUL-Multidrink

_Cheems · 2024-12-29 19:48:40 · 题解

机房大佬说这题思路上没有黑题的压迫感。

不妨拎起 1\to n 的链，链上每个点代表一棵子树。直觉上应该依次将子树遍历完再进行下去，这确实是对的。证明考虑调整法即可，假如我多次遍历该子树，则存在方案一次性遍历完，然后其它的对该子树的遍历就跳过即可。

于是考虑对一棵子树的遍历，同理进入儿子子树就应该遍历完，显然树形 dp，记 f_{u,0/1/2/3} 表示根进根出、根进儿子出、儿子进根出、儿子进儿子出地遍历完该子树是否可行。注意一个性质：f_{u,1/2} 实际上是相反的，也就是说一个成立另一个肯定成立，不妨一起记在 f_{u,1}。

转移大力分讨即可：

最后，将链上的子树方案合并起来，肯定从左到右一个个地遍历，记 g_{i,0/1} 表示遍历完链上前 i 棵子树、且最终停留在 i 子树根或儿子上是否可行。转移是容易的，留给读者思考。

输出方案按转移进行即可。复杂度 O(n)。

代码

依托答辩，难以评价。

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

const int N = 6e5 + 5;
int n, u, v, d[N], dist[N], dn;
bool vis[N], f[N][3], g[N][2]; 
vector<int> to[N], son[N], ans;

inline void init(int u, int from){
    for(auto v : to[u])
        if(v ^ from) init(v, u), vis[u] |= vis[v];
    if(u == n) vis[u] = true;
    if(vis[u]) dist[++dn] = u;
}
inline void dfs(int u){
    vis[u] = true;
    for(auto v : to[u]) 
        if(!vis[v]) dfs(v), son[u].push_back(v);
    f[u][0] = son[u].empty();

    if(!son[u].empty()){
        f[u][1] = true;
        int cnt = 0;
        for(auto v : son[u])
            if(!f[v][0]){
                if(!f[v][1]) f[u][1] = false;
                else if(++cnt > 1) f[u][1] = false;
            }
    }

    if(son[u].size() >= 2){
        f[u][2] = true;
        int cnt = 0;
        for(auto v : son[u])
            if(!f[v][0]){
                if(!f[v][1]) f[u][2] = false;
                else if(++cnt > 2) f[u][2] = false;
            }
    }
}
inline void print(int u, int id){
    //0：叶
    //1：u进v出
    //2: v进u出
    //3：v进v出 
    if(!id) ans.push_back(u);
    if(id == 1){
        ans.push_back(u);
        for(auto v : son[u]) if(!f[v][0]) print(v, 2);
        for(auto v : son[u]) if(f[v][0]) print(v, 0);
    }
    if(id == 2){
        for(auto v : son[u]) if(f[v][0]) print(v, 0);
        for(auto v : son[u]) if(!f[v][0]) print(v, 1);
        ans.push_back(u);
    }
    if(id == 3){
        int fir = 0, sec = 0;
        for(auto v : son[u]) 
            if(!f[v][0]){
                if(!fir) fir = v;
                else sec = v;
            }
        if(!fir){
            for(auto v : son[u])
                if(f[v][0]){
                    print(v, 0);
                    if(!fir) ans.push_back(u), fir = 1; 
                }
        }
        else{
            for(auto v : son[u]) if(f[v][0]) print(v, 0);
            bool fl = false;
            for(auto v : son[u])
                if(!f[v][0]){
                    if(!fl) print(v, 1), ans.push_back(u), fl = true;
                    else print(v, 2);
                }
        }

    }
}
inline void print2(int i, int id){
    if(i == 1){
        if(!id) print(dist[i], 0);
        else print(dist[i], 1);
        return ;
    }
    if(!id){
        if(g[i - 1][0] && f[dist[i]][0]) print2(i - 1, 0), print(dist[i], 0);
        else if(g[i - 1][0] && f[dist[i]][1]) print2(i - 1, 0), print(dist[i], 2);
        else if(g[i - 1][1] && f[dist[i]][0]) print2(i - 1, 1), print(dist[i], 0);
    }
    else
        if(g[i - 1][0] && f[dist[i]][1]) print2(i - 1, 0), print(dist[i], 1);
        else if(g[i - 1][0] && f[dist[i]][2]) print2(i - 1, 0), print(dist[i], 3);
        else if(g[i - 1][1] && f[dist[i]][1]) print2(i - 1, 1), print(dist[i], 1); 
}
signed main(){
    cin >> n;
    for(int i = 1; i < n; ++i) scanf("%d%d", &u, &v), to[u].push_back(v), to[v].push_back(u);
    init(1, 0);
    reverse(dist + 1, dist + 1 + dn);
    for(int i = 1; i <= dn; ++i) dfs(dist[i]);
    g[1][0] = f[dist[1]][0], g[1][1] = f[dist[1]][1];
    for(int i = 2; i <= dn; ++i){
        g[i][0] = (g[i - 1][0] & (f[dist[i]][0] | f[dist[i]][1])) | (g[i - 1][1] & f[dist[i]][0]);
        g[i][1] = (g[i - 1][0] & (f[dist[i]][1] | f[dist[i]][2])) | (g[i - 1][1] & f[dist[i]][1]);
    }
    if(!g[dn][0]) puts("BRAK"); 
    else{
        print2(dn, 0);
        for(auto i : ans) printf("%d\n", i);
    }
    return 0;
}