题意：
2756 树上的路径
时间限制: 3 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给出一棵树，求出最小的k，使得，且在树中存在路径P，使得k>= S 且 k <=E. （k为路径P上的边的权值和）
输入描述 Input Description
第一行给出N，S，E，N代表树的点数，S，E如题目描述一致
下面N-1行给出这棵树的相邻两个节点的边及其权值W
输出描述 Output Description
输出一个整数k，表示存在路径P,并且路径上的权值和 K>=S , k<=E，若无解输出-1
样例输入 Sample Input
5 10 40
2 4 80
2 3 57
1 2 16
2 5 49
样例输出 Sample Output
16
数据范围及提示 Data Size & Hint
边权W<=10000,
保证答案在int（longint）范围内,且|E-S|<=50，
树上点的个数N<=30000
————————————————————————————————————————————————————————
求树上一条路径，长度k在S到E之间，且k最小。
方法为从小到大枚举k的值，如果长度不超过k的点对数比长度不超过k-1的点对数多则一定存在长度为k的点对，则输出k并退出。
1、如果S到E的区间比较大，则可以使用二分，但是本题中只有50，可以依次枚举。
2、查找点对数为树上的点分治，和上一题相同。
3、注意init()的位置，这个地方出了错……
————————————————————————————————————————————————————————
//codevs 2756鏍戜笂鐨勮矾寰?
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm> using namespace std;
const int maxn=;
int n,S,E;
struct edge
{
int u,v,w,next;
}e[*maxn];
int head[maxn],js=,mi,jst,root;
bool vis[maxn];
int siz[maxn],mx[maxn],dis[maxn];
int ans,preans,k;
void readint(int &x)
{
char c=getchar();
int f=;
for(;c>''||c<'';c=getchar())if(c=='-')f=-f;
x=;
for(;c<=''&&c>='';c=getchar())x=x*+c-'';
x=x*f;
}
void addage(int u,int v,int w)
{
e[++js].u=u;e[js].v=v;e[js].w=w;
e[js].next=head[u];head[u]=js;
}
void init()
{
memset(vis,,sizeof(vis));
ans=;
}
void dfssize(int u,int f)
{
siz[u]=;
mx[u]=;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v!=f && !vis[v])
{
dfssize(v,u);
siz[u]+=siz[v];
if(siz[v]>mx[u])mx[u]=siz[v];
}
}
}
void dfsroot(int r,int u,int f)
{
if(siz[r]-siz[u]>mx[u])mx[u]=siz[r]-siz[u];
if(mx[u]<mi)
{
mi=mx[u];
root=u;
}
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v!=f && !vis[v])
dfsroot(r,v,u);
}
}
void dfsdis(int u,int d,int f)
{
dis[jst++]=d;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v!=f && !vis[v])dfsdis(v,d+e[i].w,u);
}
}
int calc(int u,int d)
{
jst=;
dfsdis(u,d,);
int dds=;
sort(dis,dis+jst);
int i=,j=jst-;
while(i<j)
{
while(dis[i]+dis[j]>k && i<j)j--;
dds+=j-i;
i++;
}
return dds;
}
void dfs(int u)
{
mi=n;
dfssize(u,);
dfsroot(u,u,);
ans+=calc(root,);
vis[root]=;
for(int i=head[root];i;i=e[i].next)
{
int v=e[i].v;
if(!vis[v])
{
ans-=calc(v,e[i].w);
dfs(v);
}
}
}
int main()
{
readint(n);readint(S);readint(E);
for(int u,v,w,i=;i<n;i++)
{
readint(u);readint(v);readint(w);
addage(u,v,w);addage(v,u,w);
}
init();
k=S-;
dfs();
for(int i=S;i<=E;i++)
{
preans=ans;
init();
k=i;
dfs();
if(ans>preans)
{
printf("%d\n",i);
return ;
}
}
printf("-1\n");
return ;
}