BZOJ1468: Tree

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

5

HINT

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

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

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

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
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]<F[root]) root=now;
}
void GetDeep(int now,int fa)
{
    tot[++cnt]=deep[now];
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(vis[edge[i].v]||edge[i].v==fa) continue;
        deep[edge[i].v]=deep[now]+edge[i].w;
        GetDeep(edge[i].v,now);
    }
}
int Calc(int now,int val)//now点满足条件的个数 
{
    cnt=0;deep[now]=val;//一个小技巧 
    GetDeep(now,0);
    sort(tot+1,tot+cnt+1);
    int l=1,r=cnt,NowAns=0;
    while(l<r)
    {
        if(tot[l]+tot[r]<=K) NowAns+=r-l,l++;
        else r--;
    }
    return NowAns;
}
void Solve(int now)
{
    vis[now]=1;//别忘了打标记 
    ans+=Calc(now,0);
    
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(vis[edge[i].v]) continue;
        ans-=Calc(edge[i].v,edge[i].w);
        sum=siz[edge[i].v];
        root=0;
        GetRoot(edge[i].v,0);
        Solve(edge[i].v);
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    int N=read();
    for(int i=1;i<=N-1;i++)
    {
        int x=read(),y=read(),z=read();
        AddEdge(x,y,z);
        AddEdge(y,x,z);
    }
    K=read();
    F[0]=INF;sum=N;
    //这里有个技巧,把root设置为0,f[0]=INF,那么可以解决找重心时的边界问题 
    GetRoot(1,0);
    Solve(root);
    printf("%d",ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P1351 联合权值(树形dp)

9120
来自专栏数据结构与算法

BZOJ3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛(dp)

设$f[i]$表示到第$i$个位置,该位置放了牡牛的方案,$g[i]$表示到第$i$个位置,且该位置放了牝牛的方案数

7810
来自专栏数据结构与算法

codeforces1025

首先考虑一个很显然的区间dp, $f[l][r][root]$表示$(l, r)$区间内,以$root$为根是否可行

6710
来自专栏数据结构与算法

各种数论模板 不断更新 绝对精品

1.筛法求素数 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #inclu...

35290
来自专栏懒人开发

Eventbus3代码分析(五):getDefault(),register和EventBusBuilder等

除了注解,其他都和EventBus这个类有关系了 我们先从getDefault()方法开始分析

12520
来自专栏数据结构与算法

2017.5.13阶段模拟考试

预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

35660
来自专栏ACM小冰成长之路

POJ-3866-Exclusive Access 2

ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

19680
来自专栏数据结构与算法

BZOJ2462: [BeiJing2011]矩阵模板(二维hash)

二维矩阵hash,就是对行和列分配一个不同的base,然后分别做一遍hash,这样会减少冲突的概率。

8510
来自专栏数据结构与算法

BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集)

给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长...

8210
来自专栏数据结构与算法

BZOJ3527: [Zjoi2014]力(FFT)

那么\(E_j = \sum_{i = 1}^{j - 1} q_i (i - j)^2 - \sum_{i = j + 1}^n q_i (i - j)^2\...

11220

扫码关注云+社区

领取腾讯云代金券