当前位置:网站首页>[AGC009D]Uninity
[AGC009D]Uninity
2022-07-06 11:17:00 【OneInDark】
subject
Ideas
For me , Super big problem , No idea at all ; Yes H I D \sf HID HID 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 a n s ∈ { k , k + 1 } ans\in\{k,\;k{\rm+}1\} ans∈{ 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 1 1 That's it 1 1 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 ↦ N f:V\mapsto\N f:V↦N, That is, label each dot , Satisfy for any f ( x ) = f ( y ) ( x ≠ y ) f(x)=f(y)\;(x\ne y) f(x)=f(y)(x=y), There is z ∈ path ( x , y ) z\in\text{path}(x,y) z∈path(x,y) bring f ( z ) > f ( x ) f(z)>f(x) f(z)>f(x), remember v ( f ) = max f ( x ) v(f)=\max f(x) v(f)=maxf(x), The answer is min v ( f ) \min v(f) minv(f) .
Obviously, any legal solution corresponds to such a f f f . Next, just prove , In this way f f f In turn, a set of solutions can be constructed , And the answer of this solution does not exceed v ( f ) v(f) v(f) . Using induction , A point is obviously true ; When there are multiple points , find max f ( x ) \max f(x) maxf(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 ′ ) ⩽ v ( f ) − 1 v(f')\leqslant v(f)-1 v(f′)⩽v(f)−1, So the answer of this plan does not exceed v ( f ′ ) + 1 ⩽ v ( f ) v(f')+1\leqslant v(f) v(f′)+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 ) y<f(x) y<f(x), If order f ( x ) = y f(x)=y f(x)=y after x x x The subtree of is still a legal point tree ( When only the points in the subtree are considered , Satisfying the theorem f f f mapping ), set up z z z by x x x Father in the tree , Then order again f ( z ) = max [ f ( z ) , f ( x ) ] f(z)=\max[f(z),f(x)] f(z)=max[f(z),f(x)] You can get a new legal point tree ( there f ( x ) f(x) f(x) Is the original mapping value ).
It is easy to verify the legitimacy of the scheme : Across x x x The path of , If you cross z z z It is still legal , because f ( z ) f(z) f(z) No less than the original f ( x ) f(x) f(x); No crossing z z z It is still legal , This is a prerequisite . No crossing x x x The path of , It must still be legal .
and v ( f ) v(f) v(f) It won't change . therefore f ( x ) f(x) 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 d f s \tt dfs dfs, Store which in each subtree f ( x ) f(x) f(x) It needs to be avoided ( No bigger f f f Put it “ Occlusion ” live ) that will do . in consideration of f ( x ) ⩽ log n f(x)\leqslant\log n f(x)⩽logn, It can be compressed , Time complexity O ( n ) \mathcal O(n) 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;
}
边栏推荐
- NPM an error NPM err code enoent NPM err syscall open
- The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
- Principes JDBC
- [download app for free]ineukernel OCR image data recognition and acquisition principle and product application
- The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
- windows下同时安装mysql5.5和mysql8.0
- [free setup] asp Net online course selection system design and Implementation (source code +lunwen)
- [Thesis Writing] how to write function description of jsp online examination system
- [recommended by bloggers] C MVC list realizes the function of adding, deleting, modifying, checking, importing and exporting curves (with source code)
- LeetCode #461 汉明距离
猜你喜欢
学习问题1:127.0.0.1拒绝了我们的访问
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
Use dapr to shorten software development cycle and improve production efficiency
Classes in C #
AI benchmark V5 ranking
Learning question 1:127.0.0.1 refused our visit
[recommended by bloggers] C WinForm regularly sends email (with source code)
02-项目实战之后台员工信息管理
Deoldify项目问题——OMP:Error#15:Initializing libiomp5md.dll,but found libiomp5md.dll already initialized.
CSDN markdown editor
随机推荐
Antlr4 uses keywords as identifiers
Install mysql5.5 and mysql8.0 under windows at the same time
图片上色项目 —— Deoldify
A brief introduction to the microservice technology stack, the introduction and use of Eureka and ribbon
软件测试-面试题分享
虚拟机Ping通主机,主机Ping不通虚拟机
CSDN markdown editor
Redis的基础使用
Database advanced learning notes -- SQL statement
Ansible实战系列三 _ task常用命令
Why can't STM32 download the program
Use dapr to shorten software development cycle and improve production efficiency
Learning question 1:127.0.0.1 refused our visit
[number theory] divisor
CSDN question and answer tag skill tree (I) -- Construction of basic framework
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
[recommended by bloggers] C # generate a good-looking QR code (with source code)
frp内网穿透那些事
TCP/IP协议(UDP)
【博主推荐】asp.net WebService 后台数据API JSON(附源码)