Submission #1316201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316201		boclobanchat	Mergers (JOI19_mergers)	C++20	100 / 100	800 ms	117968 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
const int INF=1e9;
int A[MAXN],sp[MAXN][20],dis[MAXN],F[MAXN],pre[MAXN],L[MAXN],R[MAXN],tdfs=0;
vector<int> ds[MAXN],vi;
bool comp(int a,int b) { return L[a]<L[b]; }
void dfs(int i,int pre)
{
	sp[i][0]=pre,L[i]=++tdfs;
	for(int j=1;j<=19;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i]) if(v!=pre)
	{
		dis[v]=dis[i]+1;
		dfs(v,i);
	}
	R[i]=tdfs;
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=19;i+1;i--)
	{
		if((x-m)&(1<<i)) a=sp[a][i];
		if((y-m)&(1<<i)) b=sp[b][i];
	}
	if(a==b) return a;
	for(int i=19;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
void dfs2(int i,int pre)
{
	for(auto v:ds[i]) if(v!=pre)
	{
		dfs2(v,i);
		F[i]+=F[v];
		if(!F[v]) vi.push_back(i),vi.push_back(v);
	}
}
int solve(vector<int> vi)
{
	if(vi.empty()) return 0;
	sort(vi.begin(),vi.end(),comp);
	int sz=vi.size();
	for(int i=0;i<sz-1;i++) vi.push_back(lca(vi[i],vi[i+1]));
	sort(vi.begin(),vi.end(),comp);
	vi.erase(unique(vi.begin(),vi.end()),vi.end());
	stack<int> st;
	int ans=0;
	for(auto v:vi)
	{
		while(!st.empty()&&L[st.top()]<=L[v]&&R[v]<=R[st.top()]) st.pop(),ans--;
		st.push(v),ans++;
	}
	int l=st.top();
	st.pop();
	while(!st.empty()) l=lca(l,st.top()),st.pop();
	if(l!=vi[0]) ans++;
	return (ans+1)/2;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int l,r;
		cin>>l>>r;
		ds[l].push_back(r),ds[r].push_back(l);
	}
	dfs(1,1);
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
		if(pre[A[i]]) F[i]++,F[pre[A[i]]]++,F[lca(i,pre[A[i]])]-=2;
		pre[A[i]]=i;
	}
	dfs2(1,1);
	cout<<solve(vi);
}

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