AcWing 4381. 翻转树边 暴力DFS

思路

可以考虑利用树上前缀的和思想来处理。实际上就是利用根节点记录反向反信息。

我们首先处理出根节点到所有点的反转次数，然后再用一个 d f s dfs dfs处理出每个节点的信息。注意第二个 d f s dfs dfs，第二个dfs 根节点往下走的时候是逆过程，根节点->当前节点的顺向边都是负贡献，反转次数+1，反之亦反。

邻接表&&链式前向星均可，输入输出都没卡，可以说非常善良了。

AC Code

#include 

const int N = 1e6 + 10;

struct node{ int v, w; };

std::vector g[N];

int book[N];

inline void solve(){
    int n = 0; std::cin >> n;
    for (int i = 1, u, v; i > u >> v;
        g[u].emplace_back(node{v, 1});
        g[v].emplace_back(node{u, 0});
    }
    std::function dfs1 = [&](int u, int fa) {
        for (node v : g[u]) {
            int nv = v.v, nw = v.w;
            if(nv == fa) continue;
            book[1] += (1 - nw);
            dfs1(nv, u);
        }
    };
    dfs1(1, 0);
    std::function dfs2 = [&](int u, int fa){
        for (node v : g[u]) {
            int nv = v.v, nw = v.w;
            if(nv == fa) continue;
            book[nv] = book[u] + (nw == 1 ? 1 : -1);
            dfs2(nv, u);
        }
    };
    dfs2(1, 0);
    int ans = 1e9 + 7;
    for(int i = 1; i