BZOJ 2599 Race(树分治)

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2599

题意：给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.

题意：每次找到当前树的重心作为树根，查找通过当前树根的路径。

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #include<ctime>

 int tot,go[],next[],first[],val[];

 int size[],F[],cnt[],a[],root,n,K,vis[];

 int dis[],ans,sz,h[],sum;

 long long sx;

 int read(){

     char ch=getchar();int t=,f=;

     while (ch<''||ch>'') {

         if (ch=='-') f=-;

         ch=getchar();

     }

     while (''<=ch&&ch<=''){

         t=t*+ch-'';

         ch=getchar();

     }

     return t*f;

 }

 void insert(int x,int y,int z){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

     val[tot]=z;

 }

 void add(int x,int y,int z){

     insert(x,y,z);

     insert(y,x,z);

 }

 void findroot(int x,int fa){

     size[x]=;F[x]=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa||vis[pur]) continue;

         findroot(pur,x);

         size[x]+=size[pur];

         F[x]=std::max(F[x],size[pur]);

     }

     F[x]=std::max(F[x],sum-size[x]);

     if (F[root]>F[x]) root=x;

 }

 void dfs1(int x,int fa){

     sx++;

     if (dis[x]>K) return;

     if (h[K-dis[x]]==sz) ans=std::min(ans,a[K-dis[x]]+cnt[x]);

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa||vis[pur]) continue;

         cnt[pur]=cnt[x]+;

         dis[pur]=dis[x]+val[i];

         dfs1(pur,x);

     }

 }

 void dfs2(int x,int fa){

     if (dis[x]>K) return;

     if (h[dis[x]]!=sz) h[dis[x]]=sz,a[dis[x]]=cnt[x];

     else a[dis[x]]=std::min(a[dis[x]],cnt[x]);

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa||vis[pur]) continue;

         dfs2(pur,x);

     }

 }

 int find(int x,int fa){

     int all=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa||vis[pur]) continue;

         all+=find(pur,x);

     }

     return all;

 }

 void query(int x){

     h[]=++sz;

     a[]=;

     vis[x]=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (vis[pur]) continue;

         dis[pur]=val[i];

         cnt[pur]=;

         dfs1(pur,x);

         dfs2(pur,x);

     }

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (vis[pur]) continue;

         root=;

         sum=find(pur,);

         findroot(pur,);

         query(root);

     }

 }

 int main(){

     n=read();K=read();

     for (int i=;i<n;i++){

         int x,y,z;

         x=read();

         y=read();

         z=read();

         x++;y++;

         add(x,y,z);

     }

     root=;

     F[]=n+;

     ans=n;

     sum=n;

     findroot(,);

     query(root);

     if (ans==n) ans=-;

     printf("%d\n",ans);

 }