正题

题目大意

有一颗树，求一条路径长度k，要求 $S\leq k\leq E$ ，求最小的k。

解题思路

其实对于每个点进行点分治，每次将整棵子树的路径加入平衡树，然后在统计一次答案。时间复杂度 $O(n^2)$ 。

之后我们发现其实每次就找该子树的重心继续，不用遍历整棵子树。时间复杂度

O (能 过)

code

#include
   
    #include
    
     #include
     
      using namespace std;const int N=100100;struct node{
   	int to,w,next;}a[N*3];set
      
        ga;int siz[N],ls[N],v[N],root,S,E,n,f[N],ans,tot,x,y,w;void addl(int x,int y,int w){
   	a[++tot].to=y;a[tot].w=w;	a[tot].next=ls[x];ls[x]=tot;}void groot(int x,int fa)//寻找重心{
   	siz[x]=1;f[x]=0;	for(int i=ls[x];i;i=a[i].next)	  if(a[i].to!=fa&&!v[a[i].to])	  {
   	  	  groot(a[i].to,x);	  	  siz[x]+=siz[a[i].to];	  	  f[x]=max(f[x],siz[a[i].to]);	  }	f[x]=max(f[x],n-siz[x]);	if (f[x]
       
        =w&&w<=E) ans=min(ans,E);		int maxs=*--ga.end();		if (w+maxs>=S){
   			int fnd=w+*ga.lower_bound(S-w);			if (S<=fnd&&fnd<=E) ans=min(ans,fnd);		}	}	for(int i=ls[x];i;i=a[i].next)	  if (!v[a[i].to]&&a[i].to!=fa)		dfs(a[i].to,x,w+a[i].w,flag);}void dp(int x){
   	v[x]=1;	ga.clear();	ga.insert(0);	for(int i=ls[x];i;i=a[i].next)	  if(!v[a[i].to])	  {
   		  dfs(a[i].to,x,a[i].w,0);//根到他的路径加入平衡树		  dfs(a[i].to,x,a[i].w,1);//统计答案	  }	for(int i=ls[x];i;i=a[i].next)	  if(!v[a[i].to])	  {
   	  	  n=siz[a[i].to];	  	  root=0;	  	  groot(a[i].to,0);//寻找重心	  	  dp(root);//从重心继续分治	  }}int main(){
   	scanf("%d%d%d",&n,&S,&E);	for(int i=1;i
        
         E) ans=-1; printf("%d",ans);}