模拟试题 树（点分治/DSU）

模拟试题 树（点分治/DSU）

Description

给出一棵树，求出最小的k，满足在树中存在路径P，使得k≥S且k≤E。（k为路径上的边的权值和）

Input

第一行给出N,S,E。N代表树的点数，S,E如题目描述一致。
下面N-1行给出这棵树的相邻两个节点的边及其权值W。

Output

输出共一行一个整数，表示答案。若无解输出-1。

Sample Input

5 10 40 2 4 80 2 3 57 1 2 16 2 5 49

Sample Output

16

Hint

【样例解释】
1到2的路径即为答案。
【数据范围】
对于20%的数据满足n≤300
对于50%的数据满足n≤3000
对于60%的数据满足n≤100000
对于以上数据，满足|E-S|≤50
对于100%的数据满足n≤100000，|E-S|≤1000000

昨天才打了一个dsu今天就忘了= =，这道题点分和dsu都可做。

点分治稍慢，个人感觉点分比较好写。可能是dsu还没打熟。。。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=100005;
struct Edge{int cnt,h[Maxn],w[Maxn*2],to[Maxn*2],next[Maxn*2];inline void add(int x,int y,int z){next[++cnt]=h[x];to[cnt]=y;w[cnt]=z;h[x]=cnt;}
}e;
#define [p]
int siz[Maxn],son[Maxn],dep[Maxn],dist[Maxn];
int prt[Maxn][17];
int ans=1<<30;
set<int>s;
void getson(int x,int fa,int Dep,int Dist){siz[x]=1;prt[x][0]=fa;dep[x]=Dep;dist[x]=Dist;for(int p=e.h[x];p;p&#[p])if(to^fa){getson(to,x,Dep+1,Dist+e.w[p]);siz[x]+=siz[to];if(siz[to]>siz[son[x]])son[x]=to;}
}
void ST(int n){int maxlog=log2(n);for(int j=1;j<=maxlog;++j)for(int i=1;i<=n;++i)if(~prt[i][j-1])prt[i][j]=prt[prt[i][j-1]][j-1];
}
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);for(int i=log2(dep[x]);i>=0;--i)if(dep[x]-(1<<i)>=dep[y])x=prt[x][i];if(x==y)return y;for(int i=log2(dep[x]);i>=0;--i)if(prt[x][i]^prt[y][i])x=prt[x][i],y=prt[y][i];return prt[x][0];
}
int getdist(int x,int y){int Lca=lca(x,y);return dist[x]+dist[y]-2*dist[Lca];
}
void statistics(int x,int lca,int S,int E){set<int>::iterator it=s.lower_bound(S+2*dist[lca]-dist[x]);if(it!&#d())ans=min(ans,*it+dist[x]-2*dist[lca]);
}
void update(int x,int lca,int S,int E,int cmd){cmd?s.insert(dist[x]),void():statistics(x,lca,S,E);for(int p=e.h[x];p;p&#[p])if(to^prt[x][0])update(to,lca,S,E,cmd);
}
void dsu(int x,int S,int E){for(int p=e.h[x];p;p&#[p])if((to^prt[x][0])&&(to^son[x]))dsu(to,S,E),s.clear();if(son[x])dsu(son[x],S,E);for(int p=e.h[x];p;p&#[p])if((to^prt[x][0])&&(to^son[x])){update(to,x,S,E,0);update(to,x,S,E,1);}statistics(x,x,S,E);s.insert(dist[x]);
}
int main(){int n,S,E;scanf("%d%d%d",&n,&S,&E);for(int i=1;i<n;++i){int x,y,z;scanf("%d%d%d",&x,&y,&z);e.add(x,y,z),e.add(y,x,z);}memset(prt,-1,sizeof(prt));getson(1,0,0,0);ST(n);dsu(1,S,E);printf("%dn",ans<=E?ans:-1);return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int Maxn=100005;
struct Edge{int cnt,h[Maxn],w[Maxn*2],to[Maxn*2],next[Maxn*2];inline void add(int x,int y,int z){next[++cnt]=h[x];to[cnt]=y;w[cnt]=z;h[x]=cnt;}
}e;
struct cmp{bool operator () (const int&A,const int &b) const {return A<b;}
};set<int,cmp>ss;
int top,s[Maxn];
#define [p]
int tmpsiz[Maxn];
bool vst[Maxn];
int ans=1<<30;
inline void stat(int x,int fa,int dist){s[++top]=dist;for(int p=e.h[x];p;p&#[p])if(!vst[to]&&(to^fa))stat(to,x,dist+e.w[p]);
}
inline void work(int x,int S,int E){ss.clear();for(int p=e.h[x];p;p&#[p])if(!vst[to]){top=0;stat(to,x,e.w[p]);for(int i=1;i<=top;++i){int p=*ss.lower_bound(S-s[i]);unt(p)&&S<=p+s[i]&&p+s[i]<=E)ans=min(ans,p+s[i]);}for(int i=1;i<=top;++i)ss.insert(s[i]);}int p=*ss.lower_bound(S);unt(p)&&S<=p&&p<=E)ans=min(ans,p);
}
inline void getroot(int x,int fa,int &mn,int &root,int totsiz){tmpsiz[x]=1;int maxsiz=0;for(int p=e.h[x];p;p&#[p])if(!vst[to]&&(to^fa)){getroot(to,x,mn,root,totsiz);tmpsiz[x]+=tmpsiz[to];maxsiz=max(maxsiz,tmpsiz[to]);}maxsiz=max(maxsiz,totsiz-tmpsiz[x]);if(maxsiz<mn)mn=maxsiz,root=x;
}
inline void Divide(int x,int S,int E,int totsiz){int mn=1<<30,root=x;getroot(x,0,mn,root,totsiz);work(root,S,E);vst[root]=1;for(int p=e.h[root];p;p&#[p])if(!vst[to])Divide(to,S,E,tmpsiz[to]);
}
int main(){int n,S,E;scanf("%d%d%d",&n,&S,&E);for(int i=1;i<n;++i){int x,y,z;scanf("%d%d%d",&x,&y,&z);e.add(x,y,z),e.add(y,x,z);}
//	work(2,S,E);Divide(1,S,E,n);printf("%dn",ans==1<<30?-1:ans);return 0;
}