【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

5

HINT

Source

LTC男人八题系列

Solution

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

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

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read()
{
    int 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;
}
#define maxn 80010
int n,root,siz,ans,stack[maxn],top,K;
struct Edgenode{int to,next,val;}edge[maxn<<1];
int head[maxn],cnt=1;
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==0) 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]=1; maxx[now]=0;
    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=0; DFSval(now,0);
    sort(stack+1,stack+top+1);
    int re=0,l=1,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,0);
    visit[now]=1;
    for (int i=head[now]; i; i=edge[i].next)
        if (!visit[edge[i].to])
            {
                ans-=Getans(edge[i].to,edge[i].val);
                root=0; siz=size[edge[i].to];
                DFSroot(edge[i].to,0); work(root);
            }
}
int main()
{
    n=read();
    for (int u,v,w,i=1; i<=n-1; i++)
        u=read(),v=read(),w=read(),insert(u,v,w);
    K=read();
    maxx[0]=siz=n;
    DFSroot(1,0);
    work(root);
    printf("%d\n",ans);
    return 0;
}

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

时间: 05-07

【BZOJ-1468】Tree 树分治的相关文章

bzoj 1468 Tree(点分治模板)

1468: Tree Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 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

[bzoj 1468] Tree

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1468 Tree Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1517  Solved: 812[Submit][Status][Discuss] Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是k

poj 1744 tree 树分治

Tree Time Limit: 1000MS   Memory Limit: 30000K       Description Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of ve

HDU 4812 D Tree 树分治+逆元+hash新姿势

题意: 给定n个点的树 K 下面n个数是点权 下面n-1行给出树边. 问: 是否存在一条路径使得路径上点权积 % mod  = K 若存在则输出路径的两端. 若存在多条路径则输出字典序最小的一条. 思路: 按树重心分治. 分成路径是否经过树重心. 然后用力码.. has[x] = u; 表示乘积为x 对应的点是u 但这样has就不能用计数器来优化清空. 所以用2个数组: has[x] = cnt; has_id[x] = u; 这样has里存的是乘积为x是否存在.has_id[x] 来记录点.

POJ 1741 Tree 树分治(点分治)

题意:给你一颗带边权树,问你其中 dis(v,u) <= k 的对数 解题思路: 首先推荐大家看 09年国家集训队漆子超 的论文 看到这题  我们可以有三种思路 第一种是枚举起点,遍历整颗树找对数    时间复杂度 为  O(n^2),空间复杂度为 O(n) 第二种是树形dp的思想     每个节点用 长度为 K 数组维护 ,递归求解  时间复杂度为 O(n ^k)空间复杂度 为 O(n) 第三种就是我们要用到的点分治的思想. 这种思想的具体思路是  先找到一个  根  对这个根进行 深搜, 找

BZOJ 2599 Race(树分治)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2599 题意:给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小. 题意:每次找到当前树的重心作为树根,查找通过当前树根的路径. 1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream>

POJ 1741 Tree(树分治)

去网上搜题解大多数都是说论文,搜了论文看了看,写的确实挺好,直接复制过来. 不过代码中有些细节还是要注意的,参考这篇http://blog.sina.com.cn/s/blog_6d5aa19a0100o73m.html一段 设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的过程均可以转化为以下

POJ1751 Tree 树分治

分析:每次找重心可以发现最多n层,每层复杂度是O(nlogn) 总体时间复杂度是O(nlog^2n) #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <

树分治基础模板以及树的重心(poj1741 tree)

好久没有更新博文了,这里更新一发~~ Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v