首页 > 其他分享 >Tree

Tree

时间:2024-11-05 21:58:03浏览次数:1  
标签:int siz Tree long cent mx

P4178 Tree

题目描述:

给定一棵 n 个节点的树,每条边有边权,求出树上两点距离小于等于 k 的点对数量。

数据范围:

\(1≤n≤4×10^4\)
\(1≤k≤2×10^4\)

说句闲话

感谢著名CB大师red_fire倾情推荐%%%
在机房三个人唇枪舌剑了一小会,我们的CB大师直接开搞线段树,而仔细研读了数据范围的本蒟蒻认为sort十分的清真,于是就有了这场对决

Solution:

首先我们不难想到像这样
“树上两点距离小于等于 k的点对数量。”
的题显然可以用淀粉质解决
废话今天可是点分治专题啊:(

我们考虑如何统计答案:对于一个点cent:把它的所有儿子vcentdis全部求出来并记录到一个数组A中,然后对A排序,排序后在上面跑一个双指针,求出对于每个l,从右往左数第一个满足\(A[l]+A[r]\le k\)的,然后这部分的贡献就是r-l

注意,尽管区间长度是r-l+1,但是[l,l]并不是一个点对,所以不能将[l,l]统计进答案

但是我们会发现这样写的话同一个y内的点对也有可能被统计进答案,我们只需要对于x的每一个儿子y,去一下y内的重就好了。

Code:

#include<bits/stdc++.h>
#define int long long
const int N=4e4+5;
using namespace std;
long long ans;
int n,m,e_cnt,k;
int head[N<<1],nxt[N<<1],to[N<<1],w[N<<1];
void add(int x,int y,int z)
{
    e_cnt++;
    to[e_cnt]=y;nxt[e_cnt]=head[x];w[e_cnt]=z;
    head[x]=e_cnt;
}
int tot,cent;
int vis[N],siz[N],mx[N],A[N],dis[N];
void get_cent(int x,int fa)
{
    siz[x]=1;mx[x]=0;
    for(int i=head[x],y;i;i=nxt[i])
    {
        y=to[i];
        if(y==fa||vis[y])continue;
        get_cent(y,x);
        siz[x]+=siz[y];
        mx[x] = mx[x] > siz[y] ? mx[x] : siz[y];
    }
    mx[x]  = mx[x] > tot-siz[x] ? mx[x] : tot-siz[x];
    cent = mx[cent] < mx[x] ? cent : x;
}
void get_ans(bool tag)
{
    sort(A+1,A+1+A[0]);
    for(int l=1,r=A[0];l<=A[0];l++)
    {
        while(A[l]+A[r]>k)r--;
        if(l<r)
        ans+= (tag ? l-r : r-l);
        if(r<l)break;
    }
    A[0]=0;
}
inline void get_dis(int x,int fa)
{
    A[++A[0]]=dis[x];
    for(int i=head[x],y;i;i=nxt[i])
    {
        y=to[i];
        if(y==fa||vis[y])continue;
        dis[y]=dis[x]+w[i];
        get_dis(y,x);
    }
}
void calc(int x)
{
    dis[x]=0;
    get_dis(x,0);
    vis[x]=1;
    get_ans(0);
    for(int i=head[x],y;i;i=nxt[i])
    {
        y=to[i];
        if(vis[y])continue;
        dis[y]=dis[x]+w[i];
        get_dis(y,x);
        get_ans(1);
    }
}
void solve(int x)
{
    calc(x);
    for(int i=head[x],y;i;i=nxt[i])
    {
        y=to[i];
        if(vis[y])continue;
        cent=0;tot=siz[y];
        get_cent(y,x);
        solve(cent);
    }
}
void work()
{
    cin>>n;
    for(int i=1,x,y,z;i<n;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    cin>>k;
    mx[cent=0]=n;
    tot=n;
    get_cent(1,0);
    solve(cent);
    printf("%lld",ans);
}
#undef int
int main()
{
    //freopen("P4178_1.in","r",stdin);
    //freopen("Tree.out","w",stdout);
    work();
    return 0;
}

标签:int,siz,Tree,long,cent,mx
From: https://www.cnblogs.com/LG017/p/18528969

相关文章

  • P4178 Tree——点分治 容斥
    Tree题目描述给定一棵\(n\)个节点的树,每条边有边权,求出树上两点距离小于等于\(k\)的点对数量。输入格式第一行输入一个整数\(n\),表示节点个数。第二行到第\(n\)行每行输入三个整数\(u,v,w\),表示\(u\)与\(v\)有一条边,边权是\(w\)。第\(n+1\)行一个整数\(k\)......
  • 转 数据结构LMS-TREE 解析
    ##sample1LMS-TREE用于oceanbase数据库的内核,与传统数据库存在很多不一致的地方包括写多份数据,支持快速写,对读支持不如传统数据库,因为特意转载如下文章https://blog.51cto.com/u_15127649/3727804 平衡二叉树、B树、B+树、B*树、LSM树简介 转载mob604756fec84d2018......
  • 数据结构 -AVL Tree
    博客主页:【夜泉_ly】本文专栏:【数据结构】欢迎点赞......
  • 【ClickHouse 探秘】你知道 ClickHouse MergeTree 引擎吗?
    ......
  • 随便写的一点BinTree模板实现
    `#pragmawarning(disable:4996)includeincludeincludeincludetemplatestructBinNode{int_depth;//节点深度int_height;//节点高度T_data;//存储的数据BinNode*_parent;//父节点BinNode*_lChild;//左子节点BinNode*......
  • L. A Game On Tree
    应该坚持问题导向你的思维疏漏之处在于,忽略了“乙烯型”的情况本题其实并不是真正的数学期望型题目,因为可以通过除上\((\frac{n(n-1)}{2})^2\)将问题转化为统计所有公共路径长度的平方和考虑拆贡献。设公共边为e1,e2,...,ek,\((|e1|+|e2|+...+|ek|)^2\)分类讨论。|ei|产生的......
  • C语言数据结构之二叉树(BINARY TREE)链式存贮的简单实现
    C语言数据结构之二叉树(BINARYTREE)链式存贮的简单实现树型数据结构在应用中非常多,效率也非常好,只是结构相对复杂,理解起来有点儿难度!!!定义数据结构typedefstruct_BTreeNodeBTreeNode;struct_BTreeNode{intval;BTreeNode*lchild,*rchild;};自定义结构体数......
  • Delphi10.3中的TreeView1的使用说明
    mySQL数据库中,所有的DataBase及其对应的Tables;最终效果: 先在设计窗口,新建根结点 再添加层级为Level1级的数据库名DataBases;varRootNode,DBNodes:TTreeNode;//先建立一个TREEVIEW使用的结点对象beginFDQuery1.Active:=false;FDQuery1.SQL.Text:='S......
  • 闯关leetcode——222. Count Complete Tree Nodes
    大纲题目地址内容解题代码地址题目地址https://leetcode.com/problems/count-complete-tree-nodes/description/内容Giventherootofacompletebinarytree,returnthenumberofthenodesinthetree.AccordingtoWikipedia,everylevel,exceptpos......
  • Java进阶学习笔记54——HashMap、LinkedHashMap、TreeMap
    HashMap集合的底层原理:HashMap跟HashSet的底层原理是一模一样的,都是基于哈希表实现的。实际上,原来学的Set系列集合的底层就是基于Map实现的,只是Set集合中的元素只要键数据,不要值数据而已。哈希表:1)JDK8之前,哈希表=数组+链表;2)JDK8开始,哈希表=数组+链表+红黑树;3)哈希表是......