CF150E Freezing with Style
\(\text{difficulty}=2.5,4\)。
\(\text{tags}=点分治,单调队列,二分\)
注意到中位数考虑直接二分答案 \(k\)，令权值 \(\ge k\) 的边的新权值为 \(1\)，权值 \(<k\) 的边的新权值为 \(-1\)，那么如果存在答案就等价于找到一条边数为 \([L,R]\) 并且边的权值之和 \(\ge 0\) 的路径。为了优化常数，首先对边的权值进行离散化，这样二分的复杂度为 \(\mathcal{O}(\log n)\) 而非 \(\mathcal{O}(\log w)\)。
考虑点分治，直接每次考虑跨过分治中心（或以分治中心为端点）的路径。最暴力的思路就是分别处理出来当前子树内到分治中心经过的边数为 \(1,2,\dots\) 的最大权值，然后与前面子树的一些到分治中心的路径拼接起来。
最暴力的方法就是直接开线段树维护区间最大值，但是总时间复杂度 \(\mathcal{O}(n\log^3 n)\)，无法接受。
实际上我们发现好像可以从小到大扫当前子树经过的边数并使用单调队列来维护之前子树拼接的路径，但是如果先遍历一个最大深度非常大的子树会导致复杂度退化。解决方法也比较简单，可以将子树按最大深度排序后按顺序处理即可，容易发现每个子树的最大深度等价于被处理了两次（插入这个子树时处理一次，考虑下一个子树时处理一次）。每次插入子树时统计答案，每个深度对应之前深度的一个区间并且区间有单调性，直接单调队列处理即可。
找出一条路径是容易的，在单调队列过程中记录一下即可。
时间复杂度 \(\mathcal{O}(n\log^2 n)\)。
code
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 100005
#define inf 0x3f3f3f3f
int n,head[N],cnt,L,R,m,b[N],low;
struct edge{
int v,nxt,val;
}e[N<<1];
inline void add(int u,int v,int w){
e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
}
bool vis[N],flag;
inline int get_siz(int x,int fa){
if(vis[x]) return 0;
int siz=1;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].v!=fa) siz+=get_siz(e[i].v,x);
return siz;
}
inline int get_wc(int x,int fa,int sum,int &wc){
if(vis[x]) return 0;
int siz=1,ms=0;
for(int i=head[x],t;i;i=e[i].nxt)
if(e[i].v!=fa) t=get_wc(e[i].v,x,sum,wc),siz+=t,ms=max(ms,t);
if(max(ms,sum-siz)<=sum/2) wc=x;
return siz;
}
int dis[N],pre[N],q[N],dis_pos[N],pre_pos[N],ansx,ansy;
inline void get_dep(int x,int fa,int d,int &dep){
if(vis[x]) return;
dep=max(dep,d);
for(int i=head[x];i;i=e[i].nxt)
if(e[i].v!=fa) get_dep(e[i].v,x,d+1,dep);
}
inline void get_dist(int x,int fa,int d,int val){
if(vis[x]) return;
if(dis[d]<val) dis[d]=val,dis_pos[d]=x;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].v!=fa) get_dist(e[i].v,x,d+1,val+(e[i].val>=low?1:-1));
}
inline void devide(int x){
if(vis[x]) return;
get_wc(x,0,get_siz(x,0),x),vis[x]=1;
vector<pair<int,int> >son;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]) continue;
son.emplace_back(make_pair(0,i)),get_dep(v,x,1,son.back().first);
}
if(!son.size()) return;
sort(son.begin(),son.end());
int lim=0;pre[0]=0,pre_pos[0]=x;
for(auto tmp:son){
int v=e[tmp.second].v,mxd=tmp.first,head=1,tail=0;
get_dist(v,x,1,e[tmp.second].val>=low?1:-1);
for(int i=0,j=lim;i<=mxd;i++){
while(head<=tail&&i+q[head]>R) head++;
if(head<=tail&&dis[i]+pre[q[head]]>=0){
flag=1;
ansx=dis_pos[i],ansy=pre_pos[q[head]];
break;
}
while(j>=0&&i+j+1>=L){
while(head<=tail&&pre[j]>=pre[q[tail]]) tail--;
q[++tail]=j;
j--;
}
}
for(int i=0;i<=mxd;i++){
if(pre[i]<dis[i]) pre[i]=dis[i],pre_pos[i]=dis_pos[i];
dis[i]=-inf;
}
lim=mxd;
if(flag) return;
}
for(int i=0;i<=lim;i++) dis[i]=pre[i]=-inf;
for(int i=head[x];i;i=e[i].nxt){
devide(e[i].v);
if(flag) return;
}
}
inline bool check(){
for(int i=0;i<N;i++) dis[i]=pre[i]=-inf,vis[i]=0;
flag=0,devide(1);
return flag;
}
int main(){
for(int i=0;i<N;i++) dis[i]=pre[i]=-inf;
read(n,L,R);
for(int i=1,u,v,w;i<n;i++)
read(u,v,w),add(u,v,w),add(v,u,w),b[++m]=w;
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
for(int i=1;i<=cnt;i++) e[i].val=lower_bound(b+1,b+m+1,e[i].val)-b;
int l=1,r=m,ans=1;
while(l<=r){
low=l+r>>1;
if(check()) l=low+1,ans=low;
else r=low-1;
}
low=ans,check();
put(' ',ansx,ansy);
return 0;
}