Submission #978009

#	Time	Username	Problem	Language	Result	Execution time	Memory
978009		happy_node	Mergers (JOI19_mergers)	C++17	0 / 100	118 ms	57864 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

const int MX=5e5+5;
int N,K;
int S[MX];
vector<int> adj[MX];

int up[MX][20];
int timer=0,tin[MX],tout[MX];

void dfs(int v, int p) {
	up[v][0]=p;
	tin[v]=++timer;
	for(int k=1;k<20;k++) {
		up[v][k]=up[up[v][k-1]][k-1];
	}
	for(auto u:adj[v]) {
		if(u==p) continue;
		dfs(u,v);
	}
	tout[v]=timer;
}

bool isAnc(int anc, int nd) {
	return tin[anc]<=tin[nd] && tout[nd]<=tout[anc];
}

int LCA(int u, int v) {
	if(isAnc(u,v)) return u;
	if(isAnc(v,u)) return v;
	for(int k=19;k>=0;k--) {
		if(up[u][k]!=0 && !isAnc(up[u][k],v)) {
			u=up[u][k];
		}
	}
	return up[u][0];
}

struct fenwick {
	int t[MX];

	void upd(int pos, int val) {
		for(int i=pos;i<=N;i+=i&-i) t[i]+=val;
	}

	int que(int pos) {
		int res=0;
		for(int i=pos;i>0;i-=i&-i) res+=t[i];
		return res;
	}

	int que(int l, int r) {
		return que(r)-que(l-1);
	}
} ft;

vector<int> pos[MX];

struct dsu {
	int par[MX];

	int find(int v) {
		return par[v]==v?v:par[v]=find(par[v]);
	}

	bool merge(int u, int v) {
		u=find(u),v=find(v);
		if(u==v) return false;
		par[u]=v;
		return true;
	}

	void prep() {
		for(int i=1;i<=N;i++) par[i]=i;
	}
} ds;

int deg[MX];

void dfs2(int v, int p) {
	for(auto u:adj[v]) {
		if(u==p) continue;
		dfs2(u,v);
	}
	int k=ft.que(tin[v],tout[v]);
	if(k>0) {
		if(p!=0) ds.merge(v,p);
	}
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>K;

	for(int i=0;i<N-1;i++) {
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(int i=1;i<=N;i++) {
		cin>>S[i];
		pos[S[i]].push_back(i);
	}

	dfs(1,0);

	for(int c=1;c<=K;c++) {
		if(pos[c].empty()) continue;
		int cur=pos[c][0];
		for(auto p:pos[c]) {
			cur=LCA(cur,p);
		}
		for(auto p:pos[c]) {
			ft.upd(tin[p],1);
			ft.upd(tin[cur],-1);
		}
	}	

	ds.prep();
	dfs2(1,0);

	set<pair<int,int>> e;
	for(int i=1;i<=N;i++) {
		for(auto j:adj[i]) {
			if(ds.find(i)!=ds.find(j)) {
				e.insert({min(i,j),max(i,j)});
			}
		}
	}

	for(auto [x,y]:e) {
		deg[x]+=1;
		deg[y]+=1;
	}

	int leafs=0;
	for(int i=1;i<=N;i++) {
		if(deg[i]==1) {
			leafs+=1;
		}
	}

	cout<<(leafs+1)/2<<'\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30