codeforces 1708E - DFS Trees

E - DFS Trees

传送门

prob.: 给一个n点m边的无向图和一个错误的求MST的代码，问以哪些点为根时求出的MST是正确的

ideas: 没有权值相等的边，结合MST的性质，当有一个环的时候，MST总是将环中最大的边舍去

考虑环上每个点为环上点集中按题给的算法最先被遍历到的点，发现可能可行的情况只有该点为最大边的端点时（即图1中的u或v）

考虑以整张图的情况，有一些点作为起点是一定不合法的（除环上u，v其他点来的方向（换个角度说只有u，v及他们非环方向的连点是可行的（即图1中绿圈中的部分）

考虑给点打标记->树上染色->树上差分（参考欣君b站视频题解）

以正确的MST建树，每个环的最大边即为不在MST上的边

对于每个点如果点权>0，表示被标记过，即至少在一个环中为非法点

考虑两种情况（如图2所示）

1. u，v的lca不是u或v，考虑对于整个数权值++再将u，v子树的权值–
2. u，v的lca是u或v，设lca==u，考虑对于u的儿子权值++，v子树的权值–

code：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

vector<int> g[N];
int pa[N], depth[N], f[N][30];
int a[N], b[N];

int Find(int x) {
    
    if (pa[x] == x) return x;
    return pa[x] = Find(pa[x]);
}

void Union(int x, int y) {
    
    int fax = Find(x);
    int fay = Find(y);
    if (fax == fay) return;
    pa[fax] = fay;
}

struct edge {
    
    int u, v;
};

vector<edge> edges, vec;

void bfs(int rt) {
    
    queue<int> que;
    que.push(rt);
    while (!que.empty()) {
    
        int tmp = que.front();
        que.pop();
        for (auto u : g[tmp]) {
    
            if (u == pa[tmp]) continue;
            depth[u] = depth[tmp] + 1;
            que.push(u);
            f[u][0] = pa[u];
            for (int k = 1; k < 20; ++k) {
    
                f[u][k] = f[f[u][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 19; k >= 0; --k) {
    
        if (depth[f[a][k]] >= depth[b]) {
    
            a = f[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 19; k >= 0; --k) {
    
        if (f[a][k] != f[b][k]) {
    
            a = f[a][k];
            b = f[b][k];
        }
    }
    return f[a][0];
}

int getPa(int x, int num) {
    
    for (int k = 19; k >= 0; --k) {
    
        if ((num >> k) & 1) x = f[x][k];
    }
    return x;
}

void dfs(int x, int sum){
    
    a[x] = sum + b[x];
    for(auto to : g[x]) {
    
        if(to == pa[x]) continue;
        dfs(to, a[x]);
    }
}

void dfsPa(int x) {
    
    for(auto to : g[x]) {
    
        if(to == pa[x]) continue;
        pa[to] = x;
        dfsPa(to);
    }
}

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) pa[i] = i;
    for (int i = 1; i <= m; ++i) {
    
        int u, v;
        cin >> u >> v;
        edges.push_back({
    u, v});
    }

    for (auto tt :edges) {
    
        int u = tt.u;
        int v = tt.v;
        if (Find(u) == Find(v)) {
    
            vec.push_back(tt);
            continue;
        }
        g[u].push_back(v);
        g[v].push_back(u);
        Union(u, v);
    }

    int rt = 1;
    pa[rt] = -1;
    dfsPa(rt);
    depth[rt] = 1, depth[0] = 0;
    pa[rt] = 0;
    bfs(rt);

    for (auto tt : vec) {
    
        int u = tt.u;
        int v = tt.v;
        if (lca(u, v) != u && lca(u, v) != v) {
    
            b[rt]++;
            b[u]--;
            b[v]--;
        } else {
    
            if (lca(u, v) == v) swap(u, v);
            int s = getPa(v, depth[v] - depth[u] - 1);
            b[s]++;
            b[v]--;
        }
    }

    dfs(rt, 0);

    for (int i = 1; i <= n; ++i) {
    
        cout << (a[i] > 0 ? 0 : 1);
    }
    return 0;
}