[AGC009D]Uninity

subject

Portal to AtCoder

Ideas

For me , Super big problem , No idea at all ; Yes $\mathsf{H}\mathsf{I}\mathsf{D}$ Come on , Garbage water problem , Make it casually .

The topic is preliminarily transformed ： Build a class point tree , Minimize the height . If you build from top to bottom , There is a conclusion $ans\in \{k,k+1\}$, However, it is completely useless . You can also consider the adjustment method of finding the center of gravity —— Obviously not. .

I thought again Bottom up Build up trees . The leaves of the original tree , There must be leaves on the dianfen tree . therefore , Adjacent to the leaves of the original tree , It is the penultimate layer of the dot tree . But further up ？ I feel , If it could be $1$ That's it $1$ . Or license ; What about going up ？ Because it is not formalized , I finally failed .

What to do in this topic , Namely Write the above thinking into a theorem . So it's the conclusion again, right . Only from the perspective of the above visual description , It's hard to clarify something .

Theorem ： set up $f:V\mapsto \mathbb{N}$, That is, label each dot , Satisfy for any $f(x)=f(y)(x\ne y)$, There is $z\in \text{path}(x,y)$ bring $f(z)>f(x)$, remember $v(f)=\max f(x)$, The answer is $\min v(f)$ .

Obviously, any legal solution corresponds to such a $f$ . Next, just prove , In this way $f$ In turn, a set of solutions can be constructed , And the answer of this solution does not exceed $v(f)$ . Using induction , A point is obviously true ; When there are multiple points , find $\max f(x)$, Obviously this is the only . Take it as the root of the pointwise tree , Induction is applied to each connected block , The answer is no more than $v(f^{\prime })⩽v(f)-1$, So the answer of this plan does not exceed $v(f^{\prime })+1⩽v(f)$, Certificate completion .

then , We can Greedy recursive processing . Its source , Is the idea of building from the bottom up , But here we can give a more concise 、 More formal proof . set up $y<f(x)$, If order $f(x)=y$ after $x$ The subtree of is still a legal point tree （ When only the points in the subtree are considered , Satisfying the theorem $f$ mapping ）, set up $z$ by $x$ Father in the tree , Then order again $f(z)=\max [f(z),f(x)]$ You can get a new legal point tree （ there $f(x)$ Is the original mapping value ）.

It is easy to verify the legitimacy of the scheme ： Across $x$ The path of , If you cross $z$ It is still legal , because $f(z)$ No less than the original $f(x)$; No crossing $z$ It is still legal , This is a prerequisite . No crossing $x$ The path of , It must still be legal .

and $v(f)$ It won't change . therefore $f(x)$ The value of is unique , It just makes the subtree become the minimum value of the legal point tree . that , On the original tree $\mathtt{d}\mathtt{f}\mathtt{s}$, Store which in each subtree $f(x)$ It needs to be avoided （ No bigger $f$ Put it “ Occlusion ” live ） that will do . in consideration of $f(x)⩽\log n$, It can be compressed , Time complexity $\mathcal{O}(n)$ .

Code

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG long for LONELINESS)
#include <cctype> // ZXY yydSISTER!!!
#include <vector>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void getMin(int &x, const int &y){
    
	if(y < x) x = y;
}

const int MAXN = 100005;
struct Edge{
    
	int to, nxt;
	Edge() = default;
	Edge(int _t, int _n): to(_t), nxt(_n){
    }
};
Edge e[MAXN<<1]; int head[MAXN], cntEdge;
void addEdge(int a, int b){
    
	e[cntEdge] = Edge(b,head[a]), head[a] = cntEdge ++;
}

int ans;
int dfs(int x, int pre){
    
	int s = 0, bad = 0;
	for(int i=head[x]; ~i; i=e[i].nxt){
    
		if((i^1) == pre) continue;
		const int &&ch = dfs(e[i].to,i);
		bad |= s&ch, s |= ch;
	}
	int chose = bad ? 32-__builtin_clz(bad) : 0;
	chose += __builtin_ffs((s>>chose)+1)-1;
	ans = max(ans,chose); return ((s>>chose)|1)<<chose;
}

int main(){
    
	int n = readint();
	memset(head+1,-1,n<<2);
	for(int i=1,a,b; i!=n; ++i){
    
		a = readint(), b = readint();
		addEdge(a,b), addEdge(b,a);
	}
	dfs(1,-1); printf("%d\n",ans);
	return 0;
}