bzoj 1468 Tree(点分治模板)

1468: Tree

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1527 Solved: 818
[Submit][Status][Discuss]

Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N（n<=40000）接下来n-1行边描述管道，按照题目中写的输入接下来是k

Output

一行，有多少对点之间的距离小于等于k

Sample Input

7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10

Sample Output

/*

思路：

最容易想到的算法是：从每个点出发遍历整棵树，统计数对个数。

由于时间复杂度O(N^2)，明显是无法满足要求的。

对于一棵有根树， 树中满足要求的一个数对所对应的一条路径，必然是以下两种情况之一：

1、经过根节点

2、不经过根节点，也就是说在根节点的一棵子树中

对于情况2，可以递归求解，下面主要来考虑情况1。

设点i的深度为Depth[i]，父亲为Parent[i]。

若i为根，则Belong[i]=-1，若Parent[i]为根，则Belong[i]=i，否则Belong[i]=Belong[Parent[i]]。

这三个量都可以通过一次BFS求得。

我们的目标是要统计：有多少对(i,j)满足i<j，Depth[i]+Depth[j]<=K且Belong[i]<>Belong[j]

如果这样考虑问题会变得比较麻烦，我们可以考虑换一种角度：

设X为满足i<j且Depth[i]+Depth[j]<=K的数对(i,j)的个数

设Y为满足i<j，Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]数对(i,j)的个数

那么我们要统计的量便等于X-Y

求X、Y的过程均可以转化为以下问题：

已知A[1],A[2],...A[m]，求满足i<j且A[i]+A[j]<=K的数对(i,j)的个数

对于这个问题，我们先将A从小到大排序。

设B[i]表示满足A[i]+A[p]<=K的最大的p(若不存在则为0)。我们的任务便转化为求出A所对应的B数组。那么，若B[i]>i，那么i对答案的贡献为B[i]-i。

显然，随着i的增大，B[i]的值是不会增大的。利用这个性质，我们可以在线性的时间内求出B数组，从而得到答案。

综上，设递归最大层数为L，因为每一层的时间复杂度均为“瓶颈”——排序的时间复杂度O(NlogN)，所以总的时间复杂度为O(L*NlogN)

然而，如果遇到极端情况——这棵树是一根链，那么随意分割势必会导致层数达到O(N)级别，对于N=10000的数据是无法承受的。因此，我们在每一棵子树中选择“最优”的点分割。所谓“最优”，是指删除这个点后最大的子树尽量小。这个点可以通过树形DP在O(N)时间内求出，不会增加时间复杂度。这样一来，即使是遇到一根链的情况时，L的值也仅仅是O(logN)的。

因此，改进后算法时间复杂度为O(Nlog^2N)，可以AC。

/*

学习思路

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 0x3f3f3f3f

#define maxn 40010

using namespace std;

struct node

{

    int to,w,next;

}e[maxn<<];

int head[maxn],vis[maxn],son[maxn],deep[maxn],f[maxn],d[maxn];

int n,cnt,root,sum,K,ans,num,x,y,z,L;

inline int read()

{

    int x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

inline void add(int u,int v,int dis)

{

    e[++num].to=v;e[num].next=head[u];

    e[num].w=dis;head[u]=num;

}

inline void init()

{

    cnt=ans=root=sum=;

    memset(head,,sizeof(head));

    memset(vis,,sizeof(vis));

    memset(deep,,sizeof(deep));

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

    {

        x=read();y=read();z=read();

        add(x,y,z);add(y,x,z);

    }

}

void get_root(int now,int fa)

{

    son[now]=;f[now]=-;

    for(int i=head[now];i;i=e[i].next)

    {

        int v=e[i].to;

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

        get_root(v,now);

        son[now]+=son[v];f[now]=max(f[now],son[v]);

    }

    f[now]=max(f[now],sum-son[now]);

    if(f[now]<f[root]) root=now;

}

void get_deep(int now,int fa)

{

    deep[++L]=d[now];

    for(int i=head[now];i;i=e[i].next)

    {

        int v=e[i].to;

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

        d[v]=d[now]+e[i].w;

        get_deep(v,now);

    }

}

int cal(int now,int dis)

{

    d[now]=dis;L=;get_deep(now,-);

    sort(deep+,deep+L+);

    int t=;

    for(int l=,r=L;l<r;)

    {

        if (deep[l]+deep[r]<=K) t+=r-l,l++;

        else r--;

    }

    return t;

}

void work(int u)

{

    ans+=cal(u,);vis[u]=;

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(vis[v]) continue;

        ans-=cal(v,e[i].w);sum=son[v];

        root=;get_root(v,);work(root);

    }

}

int main()

{

    freopen("data.txt","r",stdin);

    freopen("bzoj1468.txt","w",stdout);

    n=read();

    init();K=read();

    sum=n;f[]=inf;

    get_root(,-);

    work(root);

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

    return ;

}

代码

#include<cstdio>

#include<algorithm>

#define N 40005

using namespace std;

struct arr{int s,go,next;}a[N*];

int end[N],son[N],f[N],d[N],data[N];

int cnt,L,All,ans,i,x,y,z,n,root,K;

bool Can[N];

void add(int u,int v,int s)

{

  a[++cnt].go=v;a[cnt].next=end[u];a[cnt].s=s;end[u]=cnt;

}

void Get_root(int k,int fa)

{

  son[k]=;f[k]=;

  for (int i=end[k];i;i=a[i].next)

  {

    int go=a[i].go;

    if (go==fa||Can[go]) continue;

    Get_root(go,k);son[k]+=son[go];

    if (son[go]>f[k]) f[k]=son[go];

  }

  if (All-son[k]>f[k]) f[k]=All-son[k];

  if (f[k]<f[root]) root=k;

}

void Get_array(int k,int fa)

{

  data[++L]=d[k];

  for (int i=end[k];i;i=a[i].next)

  {

    int go=a[i].go;

    if (go!=fa&&!Can[go])

      d[go]=d[k]+a[i].s,Get_array(go,k);

  }

}

int calc(int k,int now)

{

  d[k]=now;L=;Get_array(k,-);

  int A=,l,r;

  sort(data+,data+L+);

  for (l=,r=L;l<r;)

    if (data[r]+data[l]<=K) A+=(r-l),l++;else r--;

  return A;

}

void work(int k)

{

  ans+=calc(k,);Can[k]=;

  for (int i=end[k];i;i=a[i].next)

  {

    int go=a[i].go;

    if (Can[go]) continue;

    ans-=calc(go,a[i].s);f[root=]=n+;

    All=son[go];Get_root(go,-);

    work(root);

  }

}

int main()

{

    freopen("data.txt","r",stdin);

    freopen("1468.txt","w",stdout);

  scanf("%d",&n);

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

    scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);

  scanf("%d",&K);All=n;

  f[root=]=n+;Get_root(,-);

  work(root);

  printf("%d",ans);

  return ;

}

标程

#include <bits/stdc++.h>

using namespace std;

#define PaiChuCuoWuCaiBREAK true

int main()

{

    while(PaiChuCuoWuCaiBREAK)

    {

        system("data.exe");

        system("1468.exe");

        system("bzoj1468.exe");

        if(system("fc 1468.txt bzoj1468.txt")) {cout<<"lrhdsb";break;}

    }

    return ;

}

对拍

#include <bits/stdc++.h>

using namespace std;

#define maxn 10004

#define justval 68451

#define justval_ 15641684

int l[maxn],r[maxn],n,lo,ro;

int main()

{

    freopen("data.txt","w",stdout);

    n=rand()%maxn+;printf("%d\n",n);

    for(int i=;i<n;i++) l[i]=i+;

    lo=n-,r[++ro]=;

    for(int just=;just<n;just++)

    {

        int pos=rand()%lo+;

        int pos_=rand()%ro+;

        r[++ro]=l[pos];

        printf("%d %d %d\n",l[pos],r[pos_],rand()%justval);

        for(int i=pos;i<lo;i++) l[i]=l[i+];lo--;

    }

    printf("%d\n",rand()%justval_);

    return ;

}

数据生成一棵树

巴特西