首页 > 其他分享 >科学与社会研讨课部分代码保存——树上操作拓展

科学与社会研讨课部分代码保存——树上操作拓展

时间:2024-05-30 12:02:04浏览次数:25  
标签:int work pos 拓展 rg il 研讨 lca 树上

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define For(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define INF 0x7fffffff
#define il inline
#define rg register
const int N=2e5+5,M=2e5+5;
int n,m,len;
int pos[N];
int tot,head[N];
class Edge{
    public:
        int to,next;
}e[N<<1];
il void add(rg int u,rg int v){ e[++tot].to=v, e[tot].next=head[u], head[u]=tot; }
int cnt;
int w[N],b[N],st[N],ed[N],son[N],fa[N],siz[N],dep[N],top[N];
int ord[N<<1];
il void dfs1(rg int p,rg int q){
    fa[p]=q, dep[p]=dep[q]+1, siz[p]=1, ord[++cnt]=p, st[p]=cnt;
    int owo(-1);
    for(rg int i=head[p];i;i=e[i].next){
        rg int o(e[i].to);
        if(o==q) continue;
        dfs1(o,p);
        siz[p]+=siz[o];
        if(siz[o]>owo){
            owo=siz[o];
            son[p]=o;
        }
    }
    ord[++cnt]=p, ed[p]=cnt;
}
il void dfs2(rg int p,rg int q){
    top[p]=q;
    if(!son[p]) return ;
    dfs2(son[p],q);
    for(rg int i=head[p];i;i=e[i].next){
        rg int o(e[i].to);
        if(o==fa[p] or o==son[p]) continue;
        dfs2(o,o);
    }
}
il int get_lca(rg int p,rg int q){
    while(top[p]!=top[q]){
        if(dep[top[p]]<dep[top[q]]) swap(p,q);
        p=fa[top[p]];
    }
    if(dep[p]>dep[q]) swap(p,q);
    return p;
}
class Query{
    public:
        int l,r,lca,id;
        il bool operator < (const Query &p)const{ return (pos[l]^pos[p.l]) ? pos[l]<pos[p.l] : (pos[l]&1) ? r<p.r : r>p.r; }
}q[M];
bool vis[N];
int mem[N];
int res,ans[M];
il void work(rg int o){
    vis[o] ? res-= ! --mem[w[o]] : res+= !mem[w[o]] ++;
    vis[o]^=1;
}
int main(){
    srand(time(NULL));
    scanf("%d%d",&n,&m); len=sqrt(n);
    _for(i,1,n) scanf("%d",&w[i]), b[i]=w[i], pos[i]=(i-1)/len+1;
    sort(b+1,b+n+1);
    int awa=unique(b+1,b+n+1)-(b+1);
    _for(i,1,n) w[i]=lower_bound(b+1,b+awa+1,w[i])-b;
    _for(i,1,n-1){
        int u,v; scanf("%d%d",&u,&v);
        add(u,v), add(v,u);
    }
    int root=1LL*rand()*rand()%n+1;
    dfs1(root,0), dfs2(root,root);
    _for(i,1,m){
        int u,v; scanf("%d%d",&u,&v);
        int lca=get_lca(u,v);
        if(st[u]>st[v]) swap(u,v);
        if(u==lca) q[i].l=st[u], q[i].r=st[v];
        else q[i].l=ed[u], q[i].r=st[v], q[i].lca=lca;
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    int l(1),r(0);
    _for(i,1,m){
        while(l>q[i].l) work(ord[--l]);
        while(r<q[i].r) work(ord[++r]);
        while(l<q[i].l) work(ord[l++]);
        while(r>q[i].r) work(ord[r--]);
        if(q[i].lca) work(q[i].lca);
        ans[q[i].id]=res;
        if(q[i].lca) work(q[i].lca);
    }
    _for(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

标签:int,work,pos,拓展,rg,il,研讨,lca,树上
From: https://www.cnblogs.com/Chanter/p/18222081

相关文章

  • 点阵屏幕画点函数的拓展
    众所周知,所有点阵的画图形函数,都是基于画点来实现的,都是通过画点函数封装来实现,那么这次就分享一个万能通用的模板来实现,只要你的工程有画点函数,既可直接复制以下代码目录 1.画矩形2.画三角形3.画圆4.画椭圆5.画圆弧6.画线7.画波形1.画矩形/***函数:OL......
  • FTP服务的拓展知识——基于centos7
     FTP(文件传输协议)是应用非常广泛的服务,配置简单,功能强大。在开始拓展知识的介绍之前先来简单的了解一下FTP的工作模式。FTP拥有两种连接方式管理接连模式:控制ftp服务(客户端使用随机高位端口,服务端使用21端口)数据连接模式:由客户端决定pas(关闭被动模式)在输入就启用——pa......
  • 谷歌地图 | Google I/O '24 重磅发布助力企业拓展海外市场的新功能!
    编者按:本文是GoogleI/O2024系列的一部分,该系列分享了Google年度开发者大会上最新的GoogleMapsPlatform新闻。距全球首个GoogleMapsAPI问世已近20年。它引领了网络和移动端地理空间体验的革命。从那时起,GoogleMapsPlatform始终与开发者社区携手共进,不断发展,功能......
  • 5月30日在线研讨会 | 面向智能网联汽车的产教融合解决方案
    随着智能网联汽车技术的快速发展,产业对高素质技术技能人才的需求日益增长。为了促进智能网联汽车行业的健康发展,推动教育链、人才链与产业链、创新链的深度融合,经纬恒润推出产教融合相关方案,旨在通过促进教育链与产业链的深度融合,助力中国高校汽车行业人才培养及科研平台搭建。本......
  • 【知识点】拓展欧几里得与中国剩余定理
    在上一篇文章中,我们已经熟知了有关公约数和欧几里得算法的相关事宜。详情参见:欧几里得算法求最大公约数。本文将作为上篇文章内容的一个延续,简要阐述拓展欧几里得算法和中国剩余定理。拓展欧几里得算法拓展欧几里得算法(ExtendedEuclidianAlgorithm),是欧几里得算法的扩展版本,用......
  • 热更学习笔记10~11----lua调用C#中的List和Dictionary、拓展类中的方法
    [10]Lua脚本调用C#中的List和Dictionary调用还是在上文中使用的C#脚本中Student类:lua脚本:print("------------访问使用C#脚本中的List和Dictionary-----------")student.list:Add(2024)student.list:Add(5)student.list:Add(18)locallistSize=student.list.Countprin......
  • DataFrame按条件筛选、修改数据:df.loc[]拓展
    DataFrame按条件筛选、修改数据:df.loc[]拓展创建一个DataFrame先通过字典创建一个学生信息的DataFrame。importpandasaspdStudent_dict={'姓名':['张三','李四','王五','赵六'],'性别':['男','女',......
  • 树上跳棋
    题目链接`戳我\(Solution\)对于一个点如果能够被跳到当且仅当这个点的深度\(mod\)一次跳的长度等于起始节点\(mod\)一次跳的长度假设能够被\(p1,p2\)两个点都能到达的点为\(z\)需要满足以下条件\[dep[z]<=dep[lca]\]\[dep[z]\equivdep[p1]\(mod\d1)\]\[dep[z]\equivde......
  • [笔记](更新中)树形dp-中(树上背包)
    树上背包是树形dp的常见模型,通常是分组背包的变形。引入:二叉苹果树P2015二叉苹果树题意简述:在一个二叉树中,每个边有一个权值。我们要保留\(Q\)条边组成的连通分量(必须包含根节点),求边权和最大值。我们思考,从节点\(1\)(根节点)开始保留\(Q\)条边,最大答案是什么?我们分出\(3\)种......
  • [18] C++虚幻引擎功能拓展
    Day1添加轴动作EAxis::Type//轴方向枚举//旋转输入轴UInputModifierSwizzleAxis*SwizzleAxis=NewObject<UInputModifierSwizzleAxis>(MappingContext);KeyMapping.Modifiers.Add(SwizzleAxis);//取反输入轴UInputModifierNegate*Negate=NewObject<UInputModifierNe......