codevs 2756树上的路径

题意：

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

数据范围及提示 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()的位置，这个地方出了错……

————————————————————————————————————————————————————————

  1 //codevs 2756鏍戜笂鐨勮矾寰?
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 const int maxn=30010;
  9 int n,S,E;
 10 struct edge
 11 {
 12     int u,v,w,next;
 13 }e[2*maxn];
 14 int head[maxn],js=0,mi,jst,root;
 15 bool vis[maxn];
 16 int siz[maxn],mx[maxn],dis[maxn];
 17 int ans,preans,k;
 18 void readint(int &x)
 19 {
 20     char c=getchar();
 21     int f=1;
 22     for(;c>'9'||c<'0';c=getchar())if(c=='-')f=-f;
 23     x=0;
 24     for(;c<='9'&&c>='0';c=getchar())x=x*10+c-'0';
 25     x=x*f;
 26 }
 27 void addage(int u,int v,int w)
 28 {
 29     e[++js].u=u;e[js].v=v;e[js].w=w;
 30     e[js].next=head[u];head[u]=js;
 31 }
 32 void init()
 33 {
 34     memset(vis,0,sizeof(vis));
 35     ans=0;
 36 }
 37 void dfssize(int u,int f)
 38 {
 39     siz[u]=1;
 40     mx[u]=0;
 41     for(int i=head[u];i;i=e[i].next)
 42     {
 43         int v=e[i].v;
 44         if(v!=f && !vis[v])
 45         {
 46             dfssize(v,u);
 47             siz[u]+=siz[v];
 48             if(siz[v]>mx[u])mx[u]=siz[v];
 49         }
 50     }
 51 }
 52 void dfsroot(int r,int u,int f)
 53 {
 54     if(siz[r]-siz[u]>mx[u])mx[u]=siz[r]-siz[u];
 55     if(mx[u]<mi)
 56     {
 57         mi=mx[u];
 58         root=u;
 59     }
 60     for(int i=head[u];i;i=e[i].next)
 61     {
 62         int v=e[i].v;
 63         if(v!=f && !vis[v])
 64             dfsroot(r,v,u);
 65     }
 66 }
 67 void dfsdis(int u,int d,int f)
 68 {
 69     dis[jst++]=d;
 70     for(int i=head[u];i;i=e[i].next)
 71     {
 72         int v=e[i].v;
 73         if(v!=f && !vis[v])dfsdis(v,d+e[i].w,u);
 74     }
 75 }
 76 int calc(int u,int d)
 77 {
 78     jst=0;
 79     dfsdis(u,d,0);
 80     int dds=0;
 81     sort(dis,dis+jst);
 82     int i=0,j=jst-1;
 83     while(i<j)
 84     {
 85         while(dis[i]+dis[j]>k && i<j)j--;
 86         dds+=j-i;
 87         i++;
 88     }
 89     return dds;
 90 }
 91 void dfs(int u)
 92 {
 93     mi=n;
 94     dfssize(u,0);
 95     dfsroot(u,u,0);
 96     ans+=calc(root,0);
 97     vis[root]=1;
 98     for(int i=head[root];i;i=e[i].next)
 99     {
100         int v=e[i].v;
101         if(!vis[v])
102         {
103             ans-=calc(v,e[i].w);
104             dfs(v);
105         }
106     }
107 }
108 int main()
109 {
110     readint(n);readint(S);readint(E);
111     for(int u,v,w,i=1;i<n;i++)
112     {
113         readint(u);readint(v);readint(w);
114         addage(u,v,w);addage(v,u,w);
115     }
116     init();
117     k=S-1;
118     dfs(1);    
119     for(int i=S;i<=E;i++)
120     {
121         preans=ans;
122         init();
123         k=i;
124         dfs(1);
125         if(ans>preans)
126         {
127             printf("%d\n",i);
128             return 0;
129         }
130     }
131     printf("-1\n");
132     return 0;
133 }

View Code