BZOJ1468: Tree-白红宇

BZOJ1468: Tree

阅读量：4952 次

发布时间：2019-06-11

本文共 1518 字，大约阅读时间需要 5 分钟。

Time Limit: 10 Sec Memory Limit: 64 MB

Submit: 1736 Solved: 961

[][][]

Description

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

Input

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

Output

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

Sample Input

1 6 13

6 3 9

3 5 7

4 1 3

2 4 20

4 7 2

Sample Output

HINT

Source

[ ][ ][ ]

Back

点分治，真是个神奇的东西。

对于这个题而言，求出所有的距离，再利用双指针法统计答案

具体来说就是记录两个变量，当统计出一个点到其他点的距离时

如果到$l$+到$r$的距离是满足条件的，那么$l-r$中间的点就都满足条件

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN=1e6+10;const int INF=1e7+10;inline char nc(){       static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){    char c=nc();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=nc();}    while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}    return x*f;}struct node{    int u,v,w,nxt; }edge[MAXN];int head[MAXN];int num=1;inline void AddEdge(int x,int y,int z){    edge[num].u=x;    edge[num].v=y;    edge[num].w=z;    edge[num].nxt=head[x];    head[x]=num++;}int K,F[MAXN],siz[MAXN],root,sum,vis[MAXN],tot[MAXN],cnt,deep[MAXN],ans=0;void GetRoot(int now,int fa){    siz[now]=1;    for(int i=head[now];i!=-1;i=edge[i].nxt)    {        if(edge[i].v==fa||vis[edge[i].v]) continue;        GetRoot(edge[i].v,now);        siz[now]+=siz[edge[i].v];        F[now]=max(F[now],siz[edge[i].v]);    }    F[now]=max(F[now],sum-siz[now]);    if(F[now]