比赛 20241129 评测结果 AAAAAAAAAA
题目名称 路径覆盖 最终得分 100
用户昵称 darkMoon 运行时间 0.438 s
代码语言 C++ 内存使用 9.36 MiB
提交时间 2024-11-29 11:59:34
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
auto IN = freopen("lucover.in", "r", stdin);
auto OUT = freopen("lucover.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 1e5 + 5;
int n = mread(), q = mread(), f[N][2][2], ans[N], fa[N], g[N][3];
// f_{x, 0/1, 0/1} 表示 x 点,偶/奇度数,上一个从第一个/第二个方程转移过来
vector<int> v[N];
// f[x][0] = min(f[x][0] + f[y][2], f[x][1] + min(f[y][0], f[y][1]));
// f[x][1] = min(f[x][1] + f[y][2], tmp + min(f[y][0], f[y][1]) + 1);
void dfs1(int x, int fa){
    g[x][2] = 1;
    f[x][1][0] = f[x][1][1] = g[x][1] = 0;
    f[x][0][0] = f[x][0][1] = g[x][0] = 0x3f3f3f3f;
    ::fa[x] = fa;
    for(int y : v[x]){
        if(y == fa){
            continue;
        }
        dfs1(y, x);
        f[x][0][0] = g[x][0] + g[y][2];
        f[x][0][1] = g[x][1] + min(g[y][0], g[y][1]);
        
        f[x][1][0] = g[x][1] + g[y][2];
        f[x][1][1] = g[x][0] + min(g[y][0], g[y][1]) + 1;

        g[x][2] += min(g[y][0] + 1, g[y][1]);
        g[x][0] = min(f[x][0][0], f[x][0][1]);
        g[x][1] = min(f[x][1][0], f[x][1][1]);
    }
    return;
}
void dfs2(int x, int fa){
    if(x != 1){
        int t[3] = {0};
        // t 是 fa 的 g
        t[0] = max(g[fa][0] - g[x][2], g[fa][1] - min(g[x][0], g[x][1]) - 1);
        t[1] = max(g[fa][1] - g[x][2], g[fa][0] - min(g[x][0], g[x][1]));
        t[2] = g[fa][2] - min(g[x][0] + 1, g[x][1]);
        // printf("*** %lld %lld %lld %lld %lld %lld %lld\n", x, fa, t[0], t[1], t[2]
        // , f[fa][0][0] - g[x][2], f[fa][1][1] - min(g[x][0], g[x][1]) - 1);

        f[x][0][0] = g[x][0] + t[2];
        f[x][0][1] = g[x][1] + min(t[0], t[1]);
        
        f[x][1][0] = g[x][1] + t[2];
        f[x][1][1] = g[x][0] + min(t[0], t[1]) + 1;

        g[x][2] += min(t[0] + 1, t[1]);
        g[x][0] = min(f[x][0][0], f[x][0][1]);
        g[x][1] = min(f[x][1][0], f[x][1][1]);
    }
    // printf("*** %lld %lld %lld %lld\n", x, g[x][0], g[x][1], g[x][2]);
    for(int y : v[x]){
        if(y == fa){
            continue;
        }
        dfs2(y, x);
    }
    return;
}
signed main(){
    for(int i = 1, x, y; i < n; i ++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    while(q --){
        int x = mread();
        // dfs1(x, 0);
        printf("%lld\n", g[x][2]);
    }
    return 0;
}