首页 > 其他分享 >P5007 DDOSvoid 的疑惑

P5007 DDOSvoid 的疑惑

时间:2024-03-25 14:34:09浏览次数:17  
标签:疑惑 sizes ll dfs next P5007 now DDOSvoid mod

原题链接

题解

1.具体去考虑每个集合所包含的元素及其大小个数是非常繁琐的,所以我们考虑每个元素对答案的贡献
2.
令 \(f[now]\) 代表以 \(now\) 为根节点的答案
\(sizes[now]\) 代表以 \(now\) 为根节点所包含集合的个数
更新过程如下:
\(f[now]+=f[next]*(sizes[now]+1)+f[now]*sizes[next]\)

\(size[now]+=sizes[next]*(sizes[now]+1)\)

最后 \(f[now]+=a[now],sizes[next]++\)

就像往一颗已知树插入子树的过程

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
const ll mod=1e8+7;
ll f[1000006]={0},sizes[1000006]={0};

vector<ll> G[1000006];
ll k,n;
void dfs(ll now,ll fa)
{
    for(auto next:G[now])
    {
        if(next==fa) continue;
        dfs(next,now);

        f[now]=(f[now]+f[next]*(sizes[now]+1)%mod)%mod+f[now]*(sizes[next])%mod;
        sizes[now]+=sizes[next]*(sizes[now]+1)%mod;
        f[now]%=mod;
        sizes[now]%=mod;
    }
    f[now]+=(k?now:1);
    f[now]%=mod;
    sizes[now]++;
    sizes[now]%=mod;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(ll i=1;i<n;i++)
    {
        ll x,y;
        cin>>x>>y;
        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }

    dfs(1,1);
    cout<<f[1];
    return 0;
}

标签:疑惑,sizes,ll,dfs,next,P5007,now,DDOSvoid,mod
From: https://www.cnblogs.com/pure4knowledge/p/18094323

相关文章

  • 一些程序行业的问题和解答,还有一些疑惑求助求助
    1【ChatGPT5.0发布,会代替程序员吗?】?xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx2【程序员是青春饭吗?35岁之后怎么办】35岁被淘汰的是不爱学习的,依旧可以架构和项目经理还有开发xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx3【程序......
  • 一文彻底搞懂令人疑惑的Java和JDK的版本命名!
    你对Java的版本号以及JDK的命名真正清楚嘛?比如:Java8JavaSE8.0JDK1.8……知道这些是怎么回事嘛?知道还有个Java2的说法嘛?知道还有以下说法嘛?J2SE1.3J2SE1.4……现在已经6月份了,到了9月份,一个新的长期支持版本,Java17就要发布了,啥?Java版本都到17了?不不不,我一直在用JDK......
  • [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目
    这肯定是学证明了,看这篇文章补充一下细节首先,\(m\)的范围应该是\([0,b-1]\)然后,当\(m\)取不同值的时候,\(ma\)%\(b\)一定为不同值(这个性质确实有点奇特,可以记下来)反证,如果\(m_1a\equivm_2a\:(mod\:b)\)且\(0≤m_1<m_2≤b-1\),那么就有\(b|(m_2-m_1)a\),题目给出了\(a,b\)互质,......
  • 英伟达系列显卡大解析B100、H200、L40S、A100、A800、H100、H800、V100如何选择,含架构
    英伟达系列显卡大解析B100、H200、L40S、A100、A800、H100、H800、V100如何选择,含架构技术和性能对比带你解决疑惑近期,AIGC领域呈现出一片繁荣景象,其背后离不开强大算力的支持。以ChatGPT为例,其高效的运行依赖于一台由微软投资建造的超级计算机。这台超级计算机配备了数万个NVIDIA......
  • 英伟达系列显卡大解析B100、H200、L40S、A100、A800、H100、H800、V100如何选择,含架构
    英伟达系列显卡大解析B100、H200、L40S、A100、A800、H100、H800、V100如何选择,含架构技术和性能对比带你解决疑惑近期,AIGC领域呈现出一片繁荣景象,其背后离不开强大算力的支持。以ChatGPT为例,其高效的运行依赖于一台由微软投资建造的超级计算机。这台超级计算机配备了数万个NVIDI......
  • sort排序疑惑
    今天做到了一道题是这样的:病人登记看病,编写一个程序,将登记的病人按照以下原则排出看病的先后顺序:1.老年人(年龄≥60岁)比非老年人优先看病。2.老年人按年龄从大到小的顺序看病,年龄相同的按登记的先后顺序排序。3.非老年人按登记的先后顺序看病。输入格式第1行,输入一个小于10......
  • Vue3 自定义Hooks大全:一站式解决你的疑惑!
    前言不知道喜欢vue3的小伙伴和我是不是一样,刚上手vue3的时候对自定义hooks一脸懵逼,在一些视频网站学习的时候老师讲解到自定义hooks最喜欢用加减乘除来描述自定义hooks是咋用的,可能是我理解能力比较差吧,我看了这个加减乘除的自定义hooks之后感觉跟没看一样,还是一脸懵逼,......
  • cookie和session的一些疑惑以及ai解答
    我:那么当浏览器关闭的时候,当再次访问这个地址的时候,为什么之前设置的cookie没有被删除掉?而且按照你说的这次可能会生成一个新的sessionID,那么cookie里面的其他数据,它是如何获取上一次的cookie的信息,而且它是如何知道是这个客户端访问的?而不是其他客户端?AI:当浏览器关闭时,是否删......
  • 【Sword系列】第七届全国残疾人职业技能大赛样题-网络安全-疑惑的汉字
    (文章目录)前言当铺密码通常使用汉字来隐藏信息,专门用来加密数字,不需要密钥,明文信息包含在加密后的密文中。较常见的当铺密码有两种,一种是将数字映射到对应笔画的汉字,另外一种是利用汉字的字形特征,当前汉字有多少笔画出头就转化成数字几。一、疑惑的汉字1.打开题目2.解题......
  • PWM疑惑
     #include"STC12C5A60S2.H"//runsbitleft_go=P2^1;sbitleft_xia=P2^2;sbitright_go=P2^4;sbitright_xia=P2^3;sbitLeft_motor_pwm=P2^0;//左电机控速PWMAsbitRight_motor_pwm=P2^5;//右电机控速PWMBunsignedcharspeed_val_left=0;//左电机占空比pus......