bzoj 2599 [IOI2011]Race （点分治）

【题意】

问树中长为k的路径中包含边数最少的路径所包含的边数。

【思路】

统计经过根的路径。假设当前枚举到根的第S个子树，若x属于S子树，则有：

ans<-dep[x]+min{ dep[y] },y属于前S-1个子树，dis[x]<=K

所以只需要用一个数组t[len]记录前S-1棵子树中长度为len的最少边数即可。t只用开到K的最大值。

然后分治处理子树。

【代码】

 #include<set>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt)

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 typedef long long ll;

 const int N = 1e6+;

 const int inf = 1e9;

 ll read() {

     char c=getchar();

     ll f=,x=;

     while(!isdigit(c)) {

         if(c=='-') f=-; c=getchar();

     }

     while(isdigit(c))

         x=x*+c-'',c=getchar();

     return x*f;

 }

 struct Edge {

     int v,w,nxt;

 }e[N<<];

 int en=,front[N];

 void adde(int u,int v,int w)

 {

     e[++en]=(Edge){v,w,front[u]}; front[u]=en;

 }

 int l1,l2;

 int t[N],dep[N],dis[N],ans=inf,list[N];

 int vis[N],siz[N],rt,f[N],size,n,K;

 void getroot(int u,int fa)

 {

     siz[u]=; f[u]=;

     trav(u,i) if(e[i].v!=fa&&!vis[e[i].v]){

         int v=e[i].v;

         getroot(v,u);

         siz[u]+=siz[v];

         f[u]=max(f[u],siz[v]);

     }

     f[u]=max(f[u],size-siz[u]);

     if(f[u]<f[rt]) rt=u;

 }

 void dfs(int u,int fa)

 {

     list[++l1]=u;

     trav(u,i) if(e[i].v!=fa&&!vis[e[i].v]) {

         int v=e[i].v;

         dis[v]=dis[u]+e[i].w;

         dep[v]=dep[u]+;

         dfs(v,u);

     }

 }

 void solve(int u)

 {

     vis[u]=; t[]=;

     l1=l2=;

     trav(u,i) if(!vis[e[i].v]) {

         int v=e[i].v;

         dep[v]=; dis[v]=e[i].w;

         dfs(v,-);

         FOR(j,l2+,l1) {

             if(dis[list[j]]<=K)

                 ans=min(ans,dep[list[j]]+t[K-dis[list[j]]]);

         }

         FOR(j,l2+,l1)

             if(dis[list[j]]<=K) t[dis[list[j]]]=min(t[dis[list[j]]],dep[list[j]]);

         l2=l1;

     }

     FOR(i,,l1) t[dis[list[i]]]=inf;

     trav(u,i) if(!vis[e[i].v]) {

         int v=e[i].v; rt=;

         getroot(v,-); size=siz[v];

         solve(rt);

     }

 }

 int main()

 {

     freopen("in.in","r",stdin);

     freopen("out.out","w",stdout);

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

     int u,v,w;

     FOR(i,,n-) {

         u=read()+,v=read()+,w=read();

         adde(u,v,w),adde(v,u,w);

     }

     FOR(i,,K) t[i]=n;

     size=f[]=ans=n;

     getroot(,-);

     solve(rt);

     if(ans==n) puts("-1");

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

     return ;

 }