[BZOJ2599][IOI2011]Race（点分治）

96 阅读 0 评论 64 点赞

我是靠谱客的博主热情镜子，最近开发中收集的这篇文章主要介绍[BZOJ2599][IOI2011]Race（点分治），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

我是超链接

题解：

喵喵喵交了一发好像把评测机卡了？T了？？？为什么啊啊啊？
然后进入无限debug ~~卡评测~~ 状态。。。怀疑人生无限循环，最后发现竟然是work语句传进去的不是我要的树根，而是v[i]，GGGGGGGG

这个东西一看就是点分治？
一开始的思路仅仅局限在求出来取个min，但是一看题目中的“简单路径”我就很方了，就是你求出来绕来绕去的并不是简单路径，那么我们就把这个问题转化为存在性问题
如果你要求最大值||最小值，你可以转化为判断存在性问题。并且在点分中的加加减减比较好用。
我们看看怎么加加减减吧，那些符合条件（长度为k）但是在绕弯弯的路径会在子树的筛选中筛出去，那我们要怎么筛呢？打个标记+1-1不就好啦

然后就是在缩边的时候了（找到符合的长度），如果大于的话就r–，相等的时候就设一个i从r开始倒序寻找直到不相等，这种缩边的技巧很常用哦，可以统计长度为定长的个数

总复杂度 $O(nlog^2n)$

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;
const int N=200005;
struct hh{int dis,dep;}d[N];
int tot,nxt[N*2],point[N],v[N*2],c[N*2],sum,root,k,size[N],f[N],deep[N],ans[N],num,dis[N];
bool vis[N];
void addline(int x,int y,int z)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z;
}
void getroot(int x,int fa)
{
    f[x]=0; size[x]=1;
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa && !vis[v[i]])
      {
        getroot(v[i],x);
        f[x]=max(f[x],size[v[i]]);
        size[x]+=size[v[i]];
      }
    f[x]=max(f[x],sum-f[x]);
    if (f[x]<f[root]) root=x;
}
void getdeep(int x,int fa)
{
    d[++num].dis=dis[x]; d[num].dep=deep[x];
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa && !vis[v[i]])
      {
        dis[v[i]]=dis[x]+c[i];
        deep[v[i]]=deep[x]+1;
        getdeep(v[i],x);
      }
}
int cmp(hh a,hh b){return a.dis<b.dis;}
void calc(int x,int nowdis,int nowdep,int vv)
{
    dis[x]=nowdis;deep[x]=nowdep;num=0;
    getdeep(x,0);
    sort(d+1,d+num+1,cmp);
    int l=1,r=num;
    for (;l<=r;l++)
    {
        while (l<r && d[l].dis+d[r].dis>k) r--;
        for (int i=r;d[l].dis+d[i].dis==k;i--) ans[d[l].dep+d[i].dep]+=vv;
    }
}
void work(int x)
{
    calc(x,0,0,1);
    vis[x]=1;
    for (int i=point[x];i;i=nxt[i])
      if (!vis[v[i]])
      {
        calc(v[i],c[i],1,-1);
        sum=size[v[i]]; root=0; getroot(v[i],x);
        work(root);
      }
}
int main()
{
    int n,i;
    scanf("%d%d",&n,&k);
    for (i=1;i<n;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        x++; y++; addline(x,y,z);
    }
    sum=n; root=0; f[0]=INF; getroot(1,0);
    work(root); 
    for (i=1;i<n;i++) 
      if (ans[i]){printf("%d",i); return 0;}
    printf("-1");
}