浅谈树分治：https://www.cnblogs.com/AKMer/p/10014803.html
题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3219
因为中位数也可以二分，所以这题跟WC2010重建计划差不多。不加剪枝会(TLE)。
时间复杂度：(O(nlogn))
空间复杂度：(O(n))
点分治版代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
bool vis[maxn];
int n,L,R,N,tot,mx,rt,ans,Mx,limit;
int now[maxn],pre[maxn*2],son[maxn*2],val[maxn*2];
int f[maxn],g[maxn],siz[maxn],Q[maxn],depest[maxn],V[maxn],dis[maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
void add(int a,int b,int c) {
pre[++tot]=now[a];
now[a]=tot,son[tot]=b,val[tot]=c;
}
void find_rt(int fa,int u) {
int res=0;siz[u]=1;
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[v]&&v!=fa)find_rt(u,v),res=max(res,siz[v]),siz[u]+=siz[v];
res=max(res,N-siz[u]);
if(res<mx)mx=res,rt=u;
}
void dfs(int fa,int u,int dep) {
siz[u]=1;mx=max(mx,dep);
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[v]&&v!=fa)dfs(u,v,dep+1),siz[u]+=siz[v];
}
bool cmp(int a,int b) {
return depest[a]<depest[b];
}
int calc(int v) {
if(v<limit)return -1;
return 1;
}
void make_g(int fa,int u,int dep,int len) {
if(dep>R)return;
g[dep]=max(g[dep],len);
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[v]&&v!=fa)make_g(u,v,dep+1,len+calc(val[p]));
}
bool query(int a,int b) {
int pos=a,h=0,t=0;
for(int i=1;i<=b;i++) {
while(i+pos>=L&&pos>=0) {
while(h!=t&&f[Q[t-1]]<f[pos])t--;
Q[t++]=pos,pos--;
}
while(h!=t&&i+Q[h]>R)h++;
if(h!=t&&f[Q[h]]+g[i]>=0)return 1;
}
return 0;
}
bool check(int u) {
for(int i=1;i<=depest[V[tot]];i++)f[i]=-maxn,g[i]=-maxn;
for(int i=1;i<=tot;i++) {
make_g(u,V[i],1,calc(dis[V[i]]));
if(query(depest[V[i-1]],depest[V[i]]))return 1;
for(int j=1;j<=depest[V[i]];j++)
f[j]=max(f[j],g[j]),g[j]=-maxn;
}
return 0;
}
void work(int u,int size) {
N=size,mx=rt=n+1,find_rt(0,u);
u=rt,vis[u]=1,tot=0;
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[v]) {
V[++tot]=v,mx=0,dis[v]=val[p];
dfs(u,v,1),depest[v]=min(R,mx);
}
sort(V+1,V+tot+1,cmp);
if(2*depest[V[tot]]<L)return;
int l=ans,r=Mx;
while(l<r) {
limit=(l+r+1)>>1;
if(check(u))l=limit;
else r=limit-1;
}ans=l;
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[v])work(v,siz[v]);
}
int main() {
n=read(),L=read(),R=read();
for(int i=1;i<n;i++) {
int a=read(),b=read(),c=read();
add(a,b,c),add(b,a,c);Mx=max(Mx,c);
}work(1,n);
if(!ans)puts("-1");
else printf("%d
",ans);
return 0;
}
边分治版代码如下：
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
#define fr first
#define sc second
const int maxn=2e5+5;
vector<pii>to[maxn];
vector<pii>::iterator it;
bool vis[maxn];
int siz[maxn],f[maxn],g[maxn],Q[maxn];
int now[maxn],pre[maxn*2],son[maxn*2],val[maxn*2];
int n,L,R,N,tot,mx,id,limit,Mx,ans,fake1,fake2,u1,u2,cnt;
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
void add(int a,int b,int c) {
pre[++tot]=now[a];
now[a]=tot,son[tot]=b,val[tot]=c;
}
void find_son(int fa,int u) {
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(v!=fa)find_son(u,v),to[u].push_back(make_pair(v,val[p]));
}
void rebuild() {
tot=1;memset(now,0,sizeof(now));
for(int i=1;i<=n;i++) {
int size=to[i].size();
if(size<=2) {
for(it=to[i].begin();it!=to[i].end();it++) {
pii tmp=*it;
add(i,tmp.fr,tmp.sc),add(tmp.fr,i,tmp.sc);
}
}
else {
pii u1=make_pair(++n,0),u2;
if(size==3)u2=to[i].front();
else u2=make_pair(++n,0);
add(i,u1.fr,u1.sc),add(u1.fr,i,u1.sc);
add(i,u2.fr,u2.sc),add(u2.fr,i,u2.sc);
if(size==3) {
for(int j=1;j<3;j++)
to[n].push_back(to[i].back()),to[i].pop_back();
}
else {
int p=0;
for(it=to[i].begin();it!=to[i].end();it++) {
if(!p)to[n-1].push_back(*it);
else to[n].push_back(*it);p^=1;
}
}
}
}
}
void find_edge(int fa,int u) {
siz[u]=1;
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[p>>1]&&v!=fa) {
find_edge(u,v),siz[u]+=siz[v];
if(abs(N-2*siz[v])<mx)
mx=abs(N-2*siz[v]),id=p>>1;
}
}
void dfs(int fa,int u,int dep) {
mx=max(mx,dep),siz[u]=1;
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[p>>1]&&v!=fa)dfs(u,v,dep+1),siz[u]+=siz[v];
}
int calc(int v) {
if(!v)return 0;
if(v<limit)return -1;
return 1;
}
void solve(int *a,int fa,int u,int dep,int len) {
if(dep>R)return;
a[dep]=max(a[dep],len);
for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if(!vis[p>>1]&&v!=fa)solve(a,u,v,dep+(val[p]!=0),len+calc(val[p]));
}
bool query(int a,int b) {
int pos=a,h=0,t=0;
for(int i=0;i<=b;i++) {
while(i+pos+cnt>=L&&pos>=0) {
while(h!=t&&f[Q[t-1]]<f[pos])t--;
Q[t++]=pos,pos--;
}
while(h!=t&&Q[h]+i+cnt>R)h++;
if(h!=t&&f[Q[h]]+g[i]+calc(val[id<<1])>=0)return 1;
}
return 0;
}
bool check() {
for(int i=1;i<=fake2;i++)g[i]=f[i]=-maxn;
solve(f,0,u1,0,0),solve(g,0,u2,0,0);
if(query(fake1,fake2))return 1;
return 0;
}
void work(int u,int size) {
if(size<2)return;
N=size,mx=id=n+1,find_edge(0,u);
fake1=0,fake2=0;vis[id]=1;
u1=son[id<<1],u2=son[id<<1|1];
mx=0,dfs(0,u1,0),fake1=min(R,mx);
mx=0,dfs(0,u2,0),fake2=min(R,mx);
if(fake1>fake2)swap(u1,u2),swap(fake1,fake2);
cnt=(val[id<<1]!=0);
if(fake2+fake1+cnt<L)return;
int l=ans,r=Mx;
while(l<r) {
limit=(l+r+1)>>1;
if(check())l=limit;
else r=limit-1;
}ans=l;
int tmp1=u1,tmp2=u2;
work(tmp1,siz[tmp1]),work(tmp2,siz[tmp2]);
}
int main() {
n=read(),L=read(),R=read();
for(int i=1;i<n;i++) {
int a=read(),b=read(),c=read();
add(a,b,c),add(b,a,c),Mx=max(Mx,c);
}find_son(0,1),rebuild(),work(1,n);
if(!ans)puts("-1");
else printf("%d
",ans);
return 0;
}