Submission #855187

#	Time	Username	Problem	Language	Result	Execution time	Memory
855187		ooscode	Synchronization (JOI13_synchronization)	C++17	100 / 100	296 ms	41212 KiB

synchronization

// IN THE NAME OF ALLAH
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define int ll
#define kids int tm = (tl + tr)>>1; int cl = v<<1; int cr = v<<1|1
#define test int n; cin >> n; while(n--)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
 
const int N = 1e5 + 10;
const int K = 800+10;
const ll mod = 998244353;
const ll INF = 1e18+10;
const int P = 31;
const int lg = 25;

int fen[N];
int st[N] , fn[N] , tim;
int par[N][lg];
vector<int> g[N];
int n , m , q , v , u;
int ans[N] , lst[N];
int mark[N];
vector<pii> e;

void upd(int pos , int x) {
	while(pos <= n) {
		fen[pos] += x;
		pos += pos & -pos;
	}
} 

int ask(int pos) {
	int ans = 0;
	while(pos) {
		ans += fen[pos];
		pos -= pos & -pos;
	}
	return ans;
}

void dfs(int v) {
	st[v] = ++tim;
	for(auto u : g[v]) {
		if(u == par[v][0])
			continue;

		par[u][0] = v;
		dfs(u);
	}
	fn[v] = tim;

	upd(st[v] , 1); upd(fn[v] + 1 , -1);
}

void init() {
	for(int i = 1 ; i < lg ; i++)
		for(int v = 1 ; v <= n ; v++)	
			par[v][i] = par[par[v][i-1]][i-1];
}

int get(int v) {
	for(int i = lg-1 ; ~i ; i--) {
		if((par[v][i] != 0) && ask(st[par[v][i]]) == ask(st[v]))
			v = par[v][i];
	}
	return v;
}

void upd(int ind) {
	int v = e[ind-1].F;
	int u = e[ind-1].S;

	if(v == par[u][0])
		swap(u , v);

	if(!mark[ind]) {
		ans[get(u)] += ans[v] - lst[v];
		upd(st[v] , -1); upd(fn[v]+1 , 1);
		mark[ind] = 1;
		return;
	}

	lst[v] = ans[v] = ans[get(v)];
	upd(st[v] , 1); upd(fn[v]+1 , -1);
	mark[ind] = 0;
}

void solve() {
	fast;
	cin >> n >> m >> q;

	for(int i = 1 ; i <= n ; i++)
		ans[i] = 1;

	for(int i = 1 ; i < n ; i++) {
		int v , u;
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
		e.pb({v , u});
	}

	dfs(1);
	init();

	while(m--) {
		int ind; cin >> ind;
		upd(ind);
	}

	while(q--) {
		int x;
		cin >> x;
		cout << ans[get(x)] << "\n";
	}
}

signed main()
{   
	solve();
} 

// IT'S EASY TO SEE
// CODE = LOVE

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40