Submission #519085

#	Time	Username	Problem	Language	Result	Execution time	Memory
519085		Koosha_mv	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	717 ms	55732 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2e5+99;

int n,m,d,res,cent,s1,s2,a[N],ans[N],dp[N],pd[N],mark[N],fenwik[N];
vector<int> v,g[N];

void add(int x, int val){ for(x++;x<n;x+=x&-x) fenwik[x]+=val; }
int get(int x) { int res=0; for (x++;x>0;x-=x&-x) res+=fenwik[x]; return res; }

void Add(int x){
	if(++mark[x]==1) res++;
}
void del(int x){
	if(--mark[x]==0) res--;
}
void dfs1(int u,int p,int dist){
	if(dist>=d){
		d=dist;
		cent=u;
	}
	for(auto v : g[u]){
		if(v==p) continue ;
		dfs1(v,u,dist+1);
	}
}
void find_cent(){
	cent=d=0;
	dfs1(1,0,0);
	s1=cent;
	cent=d=0;
	dfs1(s1,0,0);
	s2=cent;
}
void dfs2(int u,int p){
	dp[u]=0;
	for(auto v : g[u]){
		if(v==p) continue ;
		dfs2(v,u);
		maxm(dp[u],dp[v]+1);
	}
}
void dfs3(int u,int p){
	set<pair<int,int> > s;
	for(auto v : g[u]){
		if(v==p) continue ;
		s.insert(mp(dp[v],v));
	}
	for(auto v : g[u]){
		if(v==p) continue ;
		s.erase(mp(dp[v],v));
		pd[v]=0;
		if(s.size()){
			maxm(pd[v],(*s.rbegin()).F+1);
		}
		dfs3(v,u);
		s.insert(mp(dp[v],v));
	}
}
void dfs4(int u,int p,int d){
	int x=-1,y=-1;
	v.pb(u);
	if(pd[u]>0){
		add(max(0,d-pd[u]-1),1);
		add(d-1,-1);
	}
	if(d-dp[u]-2>=0 && get(d-dp[u]-2)==0){
		x=a[v[d-dp[u]-2]];
		Add(x);
	}
	if(d-dp[u]-1>=0 && get(d-dp[u]-1)==0){
		y=a[v[d-dp[u]-1]];
		Add(y);
	}
	maxm(ans[u],res);
	for(auto v : g[u]){
		if(v==p) continue ;
		dfs4(v,u,d+1);
	}
	if(x!=-1){
		del(x);
	}
	if(y!=-1){
		del(y);
	}
	if(pd[u]>0){
		add(max(0,d-pd[u]-1),-1);
		add(d-1,1);
	}
	v.pop_back();
}
void solve(int u){
	fill(mark,mark+N,0);
	fill(fenwik,fenwik+N,0);
	v.clear();
	pd[u]=res=0;
	
	dfs2(u,0);
	dfs3(u,0);
	/*f(i,1,n+1){
		cout<<i<<" : "<<dp[i]<<" "<<pd[i]<<endl;
	}*/
	dfs4(u,0,0);
	
}
	
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	f(i,1,n){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	f(i,1,n+1) cin>>a[i];
	find_cent();
	//cout<<s1<<" "<<s2<<endl;
	solve(s1);
	solve(s2);
	f(i,1,n+1) cout<<ans[i]<<" ";
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32