NOIP2023模拟9联测30-金牌

这篇具有很好参考价值的文章主要介绍了NOIP2023模拟9联测30-金牌。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

link

d u d_u du 表示 u u u 1 1 1 的距离。

预处理出 s u m u = ∑ v ∈ T u 2 d v − d u sum_u=\sum\limits_{v\in T_{u}}2^{d_v-d_u} sumu=vTu2dvdu

考虑两种情况

  • x x x y y y 都不是 l c a lca lca。答案就是 2 dis ⁡ ( x , y ) ∑ u ∈ T x 2 d u − d x ∑ v ∈ T y 2 d v − d y 2^{\operatorname{dis}(x,y)}\sum\limits_{u\in T_x}2^{d_u-d_x}\sum\limits_{v\in T_y}2^{d_v-d_y} 2dis(x,y)uTx2dudxvTy2dvdy,直接用 s u m sum sum 求即可。
  • 否则,就要进行换根的操作,令 x x x 为深度小的那个点,我们想要求以 x x x 的儿子(往下走可以走到 y y y)为根的 s u m sum sum。简单维护即可。具体可以参照代码。

由于要求 l c a lca lca,我采用树剖的方法,其实可以用 tarjan,我不会。

这里要卡常。

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)文章来源地址https://www.toymoban.com/news/detail-740118.html

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+1;
constexpr long long mod=998244353ll;
int n,q;
int head[N],nxt[N<<1],to[N<<1],cnt;
int dep[N],sz[N],fa[N],top[N],son[N];
int sum[N],pw[N],sum1[N];
void add(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
inline int MOD(int x){return x>=mod?x-mod:x;}
void dfs1(int u,int F)
{
    dep[u]=dep[F]+1;
    fa[u]=F;
    sz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        if(to[i]!=F){
            dfs1(to[i],u);
            sz[u]+=sz[to[i]];
            if(sz[son[u]]<sz[to[i]]) son[u]=to[i];
            sum[u]=MOD(sum[u]+sum[to[i]]);
        }
    }
    sum[u]=MOD((sum[u]<<1)+1);
}
void dfs2(int u,int t)
{
    top[u]=t;
    if(son[u]) dfs2(son[u],t);
    for(int i=head[u];i;i=nxt[i]){
        if(to[i]!=fa[u]&&to[i]!=son[u]){
            dfs2(to[i],to[i]);
        }
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]>dep[v]?v:u;
}
void dfs3(int u)
{
    int x=0;
    for(int i=head[u];i;i=nxt[i]) if(to[i]!=fa[u]) x=MOD(x+sum[to[i]]);
    for(int i=head[u];i;i=nxt[i]){
        if(to[i]!=fa[u]){
            sum1[to[i]]=MOD((MOD(MOD(x+sum1[u])+mod-sum[to[i]])<<1)+1);
            dfs3(to[i]);
        }
    }
}
int main()
{
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=MOD(pw[i-1]<<1);
    dfs1(1,0);
    dfs2(1,1);
    dfs3(1);
    cin>>q;
    for(int i=1,x,y;i<=q;i++){
        cin>>x>>y;
        int Lca=lca(x,y);
        if(x!=Lca&&y!=Lca) cout<<1ll*sum[x]*sum[y]%mod*pw[dep[x]+dep[y]-2*dep[Lca]]%mod<<"\n";
        else{
            if(dep[x]>dep[y]) swap(x,y);
            int xx=dep[y]-dep[x]-1,now=y;
            if(xx>0){
                while(top[x]!=top[now]){
                    now=top[now];
                    if(fa[now]==x) goto a;
                    now=fa[now];
                }
                now=son[x];
            }
            a:cout<<1ll*sum[y]*sum1[now]%mod*pw[dep[x]+dep[y]-2*dep[Lca]]%mod<<"\n";
        }
    }
}

到了这里,关于NOIP2023模拟9联测30-金牌的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • CSP模拟58联测20 回忆旅途的过往

    题目大意 有 n n n 个砝码,每个砝码的初始重量为 a i a_i a i ​ 。有 q q q 次操作,每次操作分为以下两种类型: 1 l r x :表示将 l l l 到 r r r 之间的所有 a i a_i a i ​ 都变成 x x x 2 l r x :查询 l l l 到 r r r 之间的所有砝码,每个砝码可以用无限次,求是否能称出质量 x x x a i a_

    2024年02月07日
    浏览(44)
  • 数据结构和算法-2023.07.03

      由于工作量加大,加之每天要写博客的内容上,深度可能没有那么深度了,但是为了保持这个日更的习惯,还是要坚持更新一些,我也发现了,其实写这个博文,更让我从某种程度上我重新的安静下来,重新的去理解和审视之前学习过的知识,之前的薄弱点在哪里,即使在

    2024年02月12日
    浏览(43)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(75)
  • 2023届计算机保研面试基础专业问题(数据结构、算法、计算机语言、计算机网络、数据库、操作系统、数学)

    以下的专业相关基础问题,是在2022年暑期准备面试过程中,断断续续准备的,最终上岸厦大啦,也希望这些内容对后面准备保研的学弟学妹们有帮助。少即是多、快即是慢,希望大家也不必太焦虑,慢慢来比较快! 堆、栈、队列、链表等数据结构 树:红黑树、二叉树的各类

    2024年02月15日
    浏览(57)
  • 软考30-上午题-数据结构-小结

    真题1: 有向图——AOV 带权有向图——AOE 真题2: 二叉排序树: 左子树 根节点 右子树。 二叉排序树中序遍历,节点有序(递增); 初始序列有序,二叉树是单支树。(无序,也可以是单支树) 真题3: 真题4: 真题5: 真题6:  真题7: prim算法 ,时间复杂度

    2024年02月20日
    浏览(30)
  • 【数据结构(30)】6.6 图的应用

    其中: 拓扑排序 以及 关键路径 针对的是一种特殊的图,称作 有向无环图 。 生成树 图中所有顶点均由边连接在一起,但是 不存在回路 的图。 包含无向图 G 所有顶点的 极小连通子图 。 极小连通子图 : 顶点的边数目在这个连通子图中的数目已经达到最小。 如果在该图中

    2024年02月01日
    浏览(38)
  • 掌握Go语言:Go语言类型转换,解锁高级用法,轻松驾驭复杂数据结构(30)

    在Go语言中,类型转换不仅仅局限于简单的基本类型之间的转换,还可以涉及到自定义类型、接口类型、指针类型等的转换。以下是Go语言类型转换的高级用法详解: Go语言类型转换的高级用法 1. 自定义类型之间的转换 在Go语言中,可以使用类型别名或自定义类型来创建新的

    2024年04月09日
    浏览(65)
  • 【洛谷 P1328】[NOIP2014 提高组] 生活大爆炸版石头剪刀布 题解(模拟+向量)

    石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。 升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势: 斯波克:《星际迷航》主角之一。 蜥

    2024年02月09日
    浏览(37)
  • 数据结构期中模拟

    1.二叉树就是度为 2 的树。(F) 二叉树的度=2 2.线性表采用链式存储表示时,所有结点之间的存储单元地址可以连续也可以不连续。(T) 在顺序表中,逻辑上相邻的元素,其物理位置一定相邻。在单链表中,逻辑上相邻的元素,其物理位置不一定相邻。 3. 队列适合解决处理顺

    2024年02月02日
    浏览(32)
  • 银行排队模拟(数据结构--队列)

    既然你点进了这篇博客,想必大概是大一 ,而且学到了队列,刚好严蔚敏老师的数据结构在讲队列的那章讲了银行排队的模拟,为什么我知道呢?因为我就是,好了谢谢你有耐心地看完我说的“废话”,下面我就简述一下,队列的实现就不讲了,很简单就是一个先进先出。

    2024年02月03日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包