树的上色
题意简述
树上有两个黑点，在每个单位时间内，每个黑点可以把自己相邻的一个白点变为黑色，求把整棵树所有点变为黑色的最短时间。
\(n\)个点，两个黑点分别为\(x,y\)。
题解
遇到两个点的题的套路，一般是先讨论简化版情况。现在我们来考虑如果只有一个黑点该怎么办
简化版问题
首先因为树是无根树，我们可以将唯一的黑点变成根节点，此时由于需要最短时间，于是就可以保证我们每一次的操作都是往下进行的，即每个节点的子节点之间不会相互影响，只能由这个节点来一个个更新，这启发我们考虑树形DP。具体的，我们设 \(f_i\) 表示在以 \(i\) 为根的子树中，若最初 \(i\) 为黑色，其余点为白色，将整棵子树变为黑色的最短时间。
现在我们考虑求解子树\(u\)，设它的子节点为\(v_1,v_2\sim v_{c}\)，此时我们只能够以某种顺序去选择这\(c\)个节点的染黑时间。说人话就是给\(v_1\sim v_c\)赋权，将\(1\sim c\)分别赋给某个节点，在赋权之后，设为\(f'_v=f_v+x\)，其中\(x\)表示给节点\(v\)赋权的值，则\(f_u=\max_{1\le i\le c}\lbrace f_{v_i} \rbrace\)。所以在树形DP的转移过程，我们就需要求解一个优秀的赋权方案，使得所有赋权之后的节点的权值最小。
引理：按照\(f_v\)的大小，从大到小的给每个\(f_v\)从小到达赋权。
说详细点，就是先按\(f_{v_i}\)从小到达排序，则\(f'_{v_i}=f_{v_i}+c-i+1\)
证明：食用贪心的邻项交换法，考虑两个节点\(j,k\)，有\(f_j<f_k\)，设需要给他们赋权为\(p,q(p<q)\)，则我们需要证明的即为\(f_j+q,f_k+p\)更优，用数学语言表达，即需证：
\[\max\lbrace f_j+q,f_k+p\rbrace\le \max\lbrace f_j+p,f_k+q \rbrace \]首先对于右边，因为\(f_j\le f_k,p<q\)，所以右式值本就为\(f_k+q\)
所以即需证\(\max\lbrace f_j+q,f_k+p\rbrace\le f_k+q\)，此时显然有\(f_k+p\le f_k+q\)，而因为\(f_j\le f_k\)，所以\(f_j+q\le f_k+q\)，故原式成立。所以贪心策略成立。
那么我们就得到了这个简化版问题的解：
\(f\)初始为\(0\)，枚举\(f\)的每一个子节点，并将其\(f\)从小到大排序，从大到小的赋权\(1\sim n\)，在赋权后的\(f'\)取最大值。
写成代码即为：
void solve(int u,int fa){
int sum=0;
f[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v!=fa&&vis[i]!=1){
solve(v,u);
}
}
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v!=fa&&vis[i]!=1)b[++sum]=f[v];
}
sort(b+1,b+sum+1);
reverse(b+1,b+sum+1);//为了代码的方便
for(int i=1;i<=sum;i++){
f[u]=max(f[u],b[i]+i);
}
}
扩展到原问题
对于原问题，将两个黑点来看，可以将树拆成两部分进行处理。而拆树的部分一定就在\(x->y\)的这条路径上。朴素的思想是枚举这一条路径断开哪一条边，然后对于断开后的两棵树的解分别求\(\max\)。时间复杂度\(O(n^2\log n)\)，可以过64分。
以单调性再优化
再来审视这个枚举的过程，设总共\(x->y\)有\(len\)条树边，设定义域为\([1,len]\)的整数的函数\(g1,g2\)，\(g1(k)\)表示切断从\(x\)出发的第\(k\)条边的答案，\(g2\)类似，则显然\(g1,g2\)都是非严格单调递增的函数，那么我们要求得一个\(k\)使得\(\max\lbrace g1(k),g2(len-k+1)\rbrace\)最小。这样考虑，随着\(k\)的不断增大，\(g1(k)\)会逐步增大，\(g2(len-k+1)\)会逐步减小，则必然存在一个值\(k\)，使得\(g1(k)\le g2(len-k+1)\)且\(g1(k+1)> g2(len-k)\)。（不存在的时候显然直接取\(k=1\)即为最优解）
显然此时的\(k\)是\(1\sim k\)中最优秀的决策，而\(k+1\)是\(k+1\sim len\)中最优秀的决策，所以最终解一定是在\(k,k+1\)中产生。而\(k\)的值显然可以二分。至此，本题就将做法优化为了一个上界为\(O(n \log^2 n)\)的优秀算法。
实际上，排序的\(\log\)完全看树的层数，随机数据下绝对跑得很快
最终的Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define N 5000005
int head[N],in,n,m,ver[N],list[N],tot=1,nxt[N],ans=1e9,x,y,vis[N],cnt,f[N],b[N],lst[N];
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void dfs(int u,int in){
list[u]=in;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if((i^1)==in){
continue;
}
dfs(v,i);
}
}
void find(){
int v=y;
while(v!=x){
lst[++cnt]=list[v];
v=ver[list[v]^1];
}
}
void solve(int u,int fa){
int sum=0;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v!=fa&&vis[i]!=1){
solve(v,u);
}
}
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v!=fa&&vis[i]!=1)b[++sum]=f[v];
}
sort(b+1,b+sum+1);
reverse(b+1,b+sum+1);
for(int i=1;i<=sum;i++){
f[u]=max(f[u],b[i]+i);
}
}
int check(int mid){
memset(f,0,sizeof f);
vis[lst[mid]]=vis[lst[mid]^1]=1;
solve(x,0);
solve(y,0);
vis[lst[mid]]=vis[lst[mid]^1]=0;
return f[x]<=f[y];
}
void init(){
cin>>n>>x>>y;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);add(v,u);
}
dfs(x,0);
find();
}
void solve(){
int l=1,r=cnt;
while(l<r){
int mid=l+r>>1;
if(check(mid)){
r=mid;
}
else {
l=mid+1;
}
ans=min(ans,max(f[x],f[y]));
}
check(l);
ans=min(ans,max(f[x],f[y]));
check(--l);
ans=min(ans,max(f[x],f[y]));
cout<<ans;
}
signed main(){
ios::sync_with_stdio(false);
init();
solve();
return 0;
}