首页 > 代码库 > bzoj1468 Tree

bzoj1468 Tree

2024-10-31 15:03:01   205人阅读

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
 
点分治裸题吧……
考虑统计经过根的路径，有两种搞法
第一种，每次提出一个子树，枚举子树中每个点到根的距离x，在平衡树中找小等于k-x的数有多少个，完了之后再把子树中所有距离扔进平衡树中
第二种，不管子树之间的关系直接把所有距离排序，用两个指针l,r就可以O(n)统计答案。因为是距离<=k，所以只要a[l]+a[r]<=k，那么所有a[l]和所有a[l]~a[r]的都可以。对答案的贡献是r-l
然后因为可能会出现重复计数，所以还要用容斥原理把路径两端点分别在同一子树内的情况减掉
反正我写的第二种……谁有事没事手写平衡树
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7fffffff#define N 40010using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}struct edge{int to,next,v;}e[10*N];int head[N],son[N],f[N],d[N],s[N];int n,k,cnt,root,sum,ans,len;bool vis[N];inline void ins(int u,int v,int w){    e[++cnt].to=v;    e[cnt].v=w;    e[cnt].next=head[u];    head[u]=cnt;} inline void insert(int u,int v,int w){    ins(u,v,w);    ins(v,u,w);}inline void getroot(int x,int fa){    son[x]=1;f[x]=0;    for(int i=head[x];i;i=e[i].next)        if (fa!=e[i].to&&!vis[e[i].to])        {            getroot(e[i].to,x);            son[x]+=son[e[i].to];            f[x]=max(f[x],son[e[i].to]);        }    f[x]=max(f[x],sum-son[x]);    if (f[x]<f[root])root=x;}inline void getd(int x,int fa){    s[++len]=d[x];    for (int i=head[x];i;i=e[i].next)        if (!vis[e[i].to]&&fa!=e[i].to)        {            d[e[i].to]=d[x]+e[i].v;            getd(e[i].to,x);        }}inline int calc(int x,int v){    d[x]=v;len=0;    getd(x,0);    sort(s+1,s+len+1);    int tt=0,l=1,r=len;    while (l<r)    {        if (s[l]+s[r]<=k)tt+=r-l,l++;        else r--;    }    return tt;}inline void solve(int x){    ans+=calc(x,0);vis[x]=1;    for(int i=head[x];i;i=e[i].next)        if (!vis[e[i].to])        {            ans-=calc(e[i].to,e[i].v);            sum=son[e[i].to];            root=0;            getroot(e[i].to,0);            solve(e[i].to);        }}int main(){    n=read();    for (int i=1;i<n;i++)    {        int x=read(),y=read(),z=read();        insert(x,y,z);    }    k=read();    f[0]=n+1;sum=n;    getroot(1,0);    solve(root);    printf("%d\n",ans);    return 0;}

 

bzoj1468 Tree


联系
我们