1 条题解

  • 0
    @ 2026-5-8 2:01:44
    #include <bits/stdc++.h>
    using namespace std;
    
    #ifdef KURUMI
        #include "algo/debug.h"
    #endif
    
    #define endl '\n'
    #define fi first
    #define se second
    #define sz(v) (int)v.size()
    #define all(v) v.begin(), v.end()
    #define filter(v) v.resize(unique(all(v)) - v.begin())
    #define dbg(x) "[" #x << " = " << x << "]" 
    
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
        return uniform_int_distribution<T2>(l, r)(rng);
    }
    template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
        if(seed == 0) return rand(l, r);
        else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
    }
    
    template<typename T> bool maximize(T &a, T b) {
        if(a < b) {
            a = b;
            return true; 
        }else return false;
    }
    template<typename T> bool minimize(T &a, T b) {
        if(a > b) {
            a = b;
            return true;
        }else return false;
    }
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ll, int> pli;
    typedef pair<ll, ll> pll;
    typedef tuple<int, int, int> tp3;
    
    const int N = 5e5 + 3;
    
    int n, m, q;
    pii edge[N];
    vector<int> adj[N];
    
    void input() {
    	cin >> n >> m >> q;
    
    	for(int i = 1; i < n; i++) {
    		int u, v; cin >> u >> v;
    		edge[i] = {u, v};
    		adj[u].push_back(v);
    		adj[v].push_back(u);
    	}
    }
    
    const int LOG = 21;
    
    int timer;
    int dep[N], tin[N], tout[N], par[N][LOG];
    int answer[N], last[N];
    bool state[N];
    
    struct FenwickTree {
    	vector<int> tr;
    	FenwickTree (int n = 0) : tr(n + 3) {}
    
    	void update(int p, int v) {
    		for(; p < sz(tr); p += p & -p) tr[p] += v;
    	}
    
    	void update(int l, int r, int v) {
    		update(l, v);
    		update(r + 1, -v);
    	}
    
    	int get(int p) {
    		int tot = 0;
    		for(; p > 0; p -= p & -p) tot += tr[p];
    		return tot;
    	}
    } active;
    
    void dfs(int u, int p) {
    	tin[u] = ++timer;
    	for(int v : adj[u]) if(v != p) {
    		dep[v] = dep[u] + 1;
    		par[v][0] = u;
    		for(int j = 1; j < LOG; j++) par[v][j] = par[par[v][j - 1]][j - 1];
    		dfs(v, u);
    	}
    	tout[u] = timer;
    }
    
    int root(int u) {
    	for(int i = LOG - 1; i >= 0; i--) {
    		if(par[u][i] && dep[par[u][i]] - active.get(tin[par[u][i]]) == dep[u] - active.get(tin[u])) {
    			u = par[u][i];
    		}  
    	}
    
    	return u;
    }
    
    void process() {
    	dfs(1, -1);
    
    	for(int i = 1; i < n; i++) {
    		auto &[u, v] = edge[i];
    		if(dep[u] > dep[v]) swap(u, v);
    	}
    
    	active = FenwickTree(n);
    	fill(answer + 1, answer + 1 + n, 1);
    
    	for(int i = 1; i <= m; i++) {
    		int d; cin >> d;
    		auto [p, u] = edge[d];
    
    		if(!state[d]) {
    			answer[root(p)] += answer[u] - last[u];
    			active.update(tin[u], tout[u], 1);
    			state[d] = true;
    		}else {
    			answer[u] = last[u] = answer[root(p)];
    			active.update(tin[u], tout[u], -1);
    			state[d] = false;
    		}
    
    		// cout << dbg(p) << dbg(u) << endl;
    		// for(int j = 1; j <= n; j++) cout << root(tin[j]) << " \n"[j == n];
    	}
    
    	while(q--) {
    		int u; cin >> u;
    		cout << answer[root(u)] << endl; 
    	}
    }
    
    int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    
        #define task "Deeto"
        if(fopen(task".inp", "r")) {
            freopen(task".inp", "r", stdin);
            freopen(task".out", "w", stdout);
        }
        
        int testcase = 1; // cin >> testcase;    
        for(int i = 1; i <= testcase; i++) {
            input();
            process();
        }
    
        cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
        cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
        
        return 0;
    }
    
    • 1

    信息

    ID
    10145
    时间
    8000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者