Submission #706222

#	Time	Username	Problem	Language	Result	Execution time	Memory
706222		alvingogo	Mergers (JOI19_mergers)	C++14	0 / 100	80 ms	22076 KiB

mergers

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

/* Merger:
first, find out the LCA of all stages

second, for each node find out whether we can cut the edge its father to the node, which can be done by storing every node's stage's LCA
if all its subtree's node's stage's LCA is in its subtree then we can cut it

last, for all the node we can build a virtual tree
we know that if we see the edges between virtual tree's node to node as a stage, the answer won't change

if we merge two stages, then the nodes on the path of the two stages are all uncuttable, so we only have to find out the minimum path cover

and i think it's equal to (the number of leaf (deg == 1) + 1) / 2, done!

guess a few coding will lead us to the ac :happy_mention:
*/
vector<int> e;
struct no{
	vector<int> ch,ch2;
	int as[20]={0};
	int dep=-1;
	int md=1e9;
	int in=0;
	int t;
};
vector<no> v;
vector<int> can;
int cnt=0;
void dfs(int r,int f){
	v[r].dep=v[f].dep+1;
	v[r].as[0]=f;
	v[r].in=cnt;
	cnt++;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs(h,r);
		}
	}
}
void dfs2(int r,int f){
	v[r].md=v[e[v[r].t]].dep;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs2(h,r);
			v[r].md=min(v[r].md,v[h].md);
		}
		
	}
	if(r!=f){
		if(v[r].md>=v[r].dep){
			can.push_back(r);
		}
	}
}
int lca(int a,int b){
	if(v[a].dep<v[b].dep){
		swap(a,b);
	}
	for(int i=19;i>=0;i--){
		if(v[v[a].as[i]].dep>=v[b].dep){
			a=v[a].as[i];
		}
	}
	if(a==b){
		return a;
	}
	for(int i=19;i>=0;i--){
		if(v[a].as[i]!=v[b].as[i]){
			a=v[a].as[i];
			b=v[b].as[i];
		}
	}
	return v[a].as[0];
}
bool cmp(int a,int b){
	return v[a].in<v[b].in;
}
int bvt(vector<int> x,int flag){
	sort(x.begin(),x.end(),cmp);
	int u=x.size();
	for(int i=1;i<u;i++){
		x.push_back(lca(x[i],x[i-1]));
	}
	sort(x.begin(),x.end(),cmp);
	if(flag==1){	
		x.erase(unique(x.begin(),x.end()),x.end());
		u=x.size();
		for(int i=0;i<u-1;i++){
			int z=lca(x[i],x[i+1]);
			v[z].ch2.push_back(x[i+1]);
			v[x[i+1]].ch2.push_back(z);
		}
	}
	return x[0];
}
int main(){
	AquA;
	int n,k;
	cin >> n >> k;
	v.resize(n);
	e.resize(k);
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		v[a].ch.push_back(b);
	}
	dfs(0,0);
	for(int i=1;i<20;i++){
		for(int j=0;j<n;j++){
			v[j].as[i]=v[v[j].as[i-1]].as[i-1];
		}
	}
	vector<vector<int> > gg(k);
	for(int i=0;i<n;i++){
		int a;
		cin >> a;
		a--;
		v[i].t=a;
		gg[a].push_back(i);
	}
	for(int i=0;i<k;i++){
		e[i]=bvt(gg[i],0);
	}
	dfs2(0,0);
	if(!can.size()){
		cout << 0 << "\n";
		return 0;
	}
	if(can.size()==1){
		cout << 1 << "\n";
		return 0;
	}
	bvt(can,1);
	int ans=0;
	for(auto h:can){
		if(v[h].ch2.size()==1){
			ans++;
		}
	}
	cout << (ans+1)/2 << '\n';
	return 0;
}

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