P6118 [joi 2019 final] solution to the problem of Zhenzhou City

A summary of the problem

• There is a tree with $N$ A tree at the top .

• Align with the vertex $x$ Vertices with a unique distance become unique .

• For each vertex, answer the number of tag types of unique cities .

about $4\%$ The data of

Do for each vertex DFS or BFS.

Take a and vertex $x$ The vertex with the greatest distance , Set to $D$, The unique feature is $(D,x)$ On the path , If any , about $(D,x)$ route , Find a subtree that branches on the way , For the maximum depth of the branching subtree , Candidate unique cities disappear , The last remaining vertices are unique .

By the way , Give Way $D1$ and $D2$ Is the endpoint of the diameter of the tree （ The two points with the longest distance are right ）.

For any vertex $x$,$D1$ and $D2$ At least one of them is Li $x$ The farthest vertex ,

From the top $D1$ Conduct DFS To determine each vertex $x$ Whether in $(D1,x)$ There are unique characteristics in the path , Yes $D2$ Perform the same DFS To get the correct answer for each vertex ,

From the maximum depth column of each subtree, we can see $(D,x)$ Unique features on the path , Each time through DFS One side of , This column will change the number of constant elements after it .

Set this column as $A$, The problem is ：

Given many changes $A$ Query for ( But only the last element ), For each $p(1\le p\le |A|),p-A_p\le j<p$, When satisfied $j$ When disabled , Not forbidden $j$ Set $|A|$ Set to $S$,$S$ The element corresponds to a unique feature .

Complexity $O(N^2)$.

about $36\%$ The data of

There is only one type of vertex label , Judge whether there are unique characteristics , Just judge $S$ Is it empty .

When they arrive in $(D,x)$ The vertex of the path $x$ when , Keep the row with the maximum depth of the subtree growing from outside （ Namely reservation $A$ The last line ）,

Let's call it $A^{\prime }$, By comparison $S$ The minimum value of is from $x$ The maximum depth of the growing subtree to find the answer ,

Find the maximum depth of each subtree in advance , Add to... As you go down the edge $A^{\prime }$ At the end is the maximum depth of the subtree brother of the subtree that just fell .

$S$ The minimum value of is the original set or $|A^{\prime }|+1$, Sure $O(1)$ Go down once ,

Complexity $O(N)$.

about $68\%$ The data of

All labels are different , Just need to know $|S|$ Size .

For each $p(1\le p\le |A|)$ Don't use satisfaction $p-A_p\le j<p$ Of $j$,

however , Prepare auxiliary array $B$, For each $p(1\le p\le |A|),B_j\leftarrow B_j+1$ among $j$ Satisfy $p-A_p\le j<p$, then , Calculation $j$ bring $B_j=0$.

$A$ Element modification corresponding to B Interval addition query , If $B$ The sum of the interval addition of becomes $0$ The counting of elements can be completed at a high speed, which is better .

because $B$ The element of is always $0$ Or more , So just check $\min \{B\}=0$ And calculate $min$ The elements of .

It can be done through the line segment tree ,$O(\log N)$ Updated once ,

The update is $N$ Time , So overall $O(N\log N)$.

about $100\%$ The data of

change $A$ Query for （ But only the last element ）, When it comes to vertices $x$ when , It holds $A^{\prime }$ From the top $x$ Return to the parent node , Keep $A$.

There are some questions in the question : “ When you walk down , Add to $A^{\prime }$ At the end is the maximum depth of the subtree of your brother who just dropped the subtree .”

Add to $A^{\prime }$ The elements at the end increase monotonically , When moving to DFS When the brothers in the tree , see $A$ The change of the last element , except $p$ Other elements may come from $S$ Disappear but not increase ,

When returning to the vertex of the parent node , If you look at $A$ The change of the last element ,$S$ The elements of may disappear but will not increase .

It can be seen from the above that ,$S$ The number of times the element of is increased is $N$ Time , therefore , Reduce the number of times by $O(N)$ To achieve .

$S$ Operations on can be represented by stacks , So every time $O(1)$,

When $S$ When the elements of increase or decrease , You can update the number of label types by changing the label set of the corresponding vertex .

Complexity $O(N)$.

AC code:

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

#define int ll
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy {
    } cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&) {
    return cd;}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)) {
    return cd;}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p) {
    os<<"("<<p.first<<","<<p.second<<")";return os;}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v) {
    os<<"{";REP(i,(int)v.size()) {
    if(i)os<<",";os<<v[i];}os<<"}";return os;}

inline ll read() {
    ll i;scanf("%"  SCNd64,&i);return i;}

inline void printSpace() {
    printf(" ");}

inline void printEoln() {
    printf("\n");}

inline void print(ll x,int suc=1) {
    printf("%" PRId64,x);if(suc==1)printEoln();if(suc==2)printSpace();}

inline string readString() {
    static char buf[3341000];scanf("%s",buf);return string(buf);}

inline char* readCharArray() {
    
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
inline void chmax(T& a,U b) {
    if(a<b)a=b;}

template<class T,class U>
inline void chmin(T& a,U b) {
    if(b<a)a=b;}

template<class T>
inline T Sq(const T& t) {
    return t*t;}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

const int Nmax=200010;
vi tr[Nmax];
int ans[Nmax];
int col[Nmax],cnt[Nmax],curAns,stBuf[Nmax],stS;

inline void AddCol(int c) {
    if(cnt[c]==0)curAns++;cnt[c]++;}

inline void DelCol(int c) {
    cnt[c]--;if(cnt[c]==0)curAns--;}

inline void Push(int v) {
    stBuf[stS++]=v;AddCol(col[v]);}

inline bool Empty() {
    return stS==0;}

inline int Last() {
    return stBuf[stS-1];}

inline void Pop() {
    DelCol(col[Last()]);stS--;}

inline void dfs1(int v,int p,int d,vi&dist) {
    
	dist[v]=d;
	for(auto to:tr[v])if(to!=p)dfs1(to,v,d+1,dist);
}

int dep[Nmax];
inline int dfs2(int v,int p) {
    
	int res=0;
	for(auto to:tr[v])if(to!=p)chmax(res,dfs2(to,v));
	return dep[v]=res+1;
}

inline void dfs3(int v,int p,const vi&dist) {
    
	vector<pi> ch;
	for(auto to:tr[v]) if(to!=p)ch.EB(dep[to],to);
	if(!ch.empty()) {
    
		swap(ch[0],*max_element(ALL(ch)));
		int len=ch.size()>1?max_element(ch.begin()+1,ch.end())->first:0;
		for(auto c:ch) {
    
			int to=c.second;
			while(!Empty() && dist[Last()]>=dist[v]-len) Pop();
			Push(v);
			dfs3(to,v,dist);
			if(!Empty() && Last()==v) Pop();
			chmax(len,c.first);
		}
		while(!Empty() && dist[Last()]>=dist[v]-len) Pop();
	}
	chmax(ans[v],curAns);
}

inline void Solve(int root,const vi&dist) {
    
	assert(Empty());
	dfs2(root,-1);
	dfs3(root,-1,dist);
}

signed main() {
    
	int n=read(),k=read();
	int root;
	REP(_,n-1) {
    
		int a=read()-1,b=read()-1;
		tr[a].PB(b);
		tr[b].PB(a);
	}
	REP(i,n) col[i]=read()-1;
	vi dist(n);
	dfs1(0,-1,0,dist);
	root= max_element(ALL(dist)) - dist.begin();
	dfs1(root,-1,0,dist);
	Solve(root,dist);
	root= max_element(ALL(dist)) - dist.begin();
	dfs1(root,-1,0,dist);
	Solve(root,dist);
	REP(i,n) print(ans[i]);
	return 0;
}