【BZOJ-1468】Tree 树分治

1468: Tree

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1025 Solved: 534
[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

HINT

Source

LTC男人八题系列

Solution

写LTC还不如直接写ACRush,楼教主的男人八题.暑假看过什么都看不懂,现在似乎可以做了?

裸的树分治,统计一下路径的权值和,排序计算答案即可

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int read()

{

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

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

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

    return x*f;

}

#define maxn 80010

int n,root,siz,ans,stack[maxn],top,K;

struct Edgenode{int to,next,val;}edge[maxn<<];

int head[maxn],cnt=;

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

{cnt++; edge[cnt].val=w; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}

void insert(int u,int v,int w)

{add(u,v,w);add(v,u,w);}

int gcd(int a,int b)

{if (b==) return a; return gcd(b,a%b);}

int size[maxn],maxx[maxn],val[maxn]; bool visit[maxn];

void DFSroot(int now,int last)

{

    size[now]=; maxx[now]=;

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

        if (edge[i].to!=last && !visit[edge[i].to])

            {

                DFSroot(edge[i].to,now);

                size[now]+=size[edge[i].to];

                maxx[now]=max(maxx[now],size[edge[i].to]);

            }

    maxx[now]=max(maxx[now],siz-size[now]);

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

}

void DFSval(int now,int last)

{

    stack[++top]=val[now];

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

        if (edge[i].to!=last && !visit[edge[i].to])

            {

                val[edge[i].to]=val[now]+edge[i].val;

                DFSval(edge[i].to,now);

            }

}

int Getans(int now,int va)

{

    val[now]=va; top=; DFSval(now,);

    sort(stack+,stack+top+);

    int re=,l=,r=top;

    while (l<r) if (stack[l]+stack[r]<=K) re+=r-l,l++; else r--;

    return re;

}

void work(int now)

{

    ans+=Getans(now,);

    visit[now]=;

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

        if (!visit[edge[i].to])

            {

                ans-=Getans(edge[i].to,edge[i].val);

                root=; siz=size[edge[i].to];

                DFSroot(edge[i].to,); work(root);

            }

}

int main()

{

    n=read();

    for (int u,v,w,i=; i<=n-; i++)

        u=read(),v=read(),w=read(),insert(u,v,w);

    K=read();

    maxx[]=siz=n;

    DFSroot(,);

    work(root);

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

    return ;

}

吃饭前想10分钟Rush出来...手速不够TAT

秒客网