【每日一题】点权和

点权和

https://ac.nowcoder.com/acm/problem/14393

题意:




思路:

首先感谢 a^-^a 大佬,我是看了他的博客,思路和注释都很清晰
他的博客


















#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 19260817;
int n,m;
ll now[N];//当前节点被操作的次数
ll son[N];//当前节点的儿子节点们被操作的次数
ll gson[N];//当前节点的孙子节点们被操作的次数

int fa[N],sz[N];//fa[u] = v,表示u的父节点为v,没有时为0;sz[i],节点i的儿子节点个数

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1,u;i < n;i++){
        scanf("%d",&u);
        fa[i + 1] = u;
        sz[u]++;
    }
    ll ans = 0;
    for(int i = 1,u;i <= m;i++){
        scanf("%d",&u);

        now[u]++;//当前节点被操作了一次
        if(fa[u]) son[fa[u]]++;//若当前节点有父节点,则告知它的父节点:你的儿子节点被操作了一次
        if(fa[fa[u]]) gson[fa[fa[u]]]++;//若当前节点存在爷爷节点,则告知它的爷爷节点,你的孙子节点被操作了一次

        //仅仅对节点u操作,影响的只有u本身,u的父节点以及u的儿子节点
        //因此将对答案的贡献拆分为三部分:

        //1.父节点对答案的贡献
        ll sum = (now[fa[u]] + son[fa[u]] + now[fa[fa[u]]]) % mod;

        //2.u本身
        sum = ( sum + (now[u] + son[u] + now[fa[u]]) % mod ) % mod;

        //3.u的儿子节点们
        sum = ( sum + (son[u] + gson[u] + sz[u]*now[u]%mod)%mod) % mod;

        ans = ( ans + (sum * i)%mod ) % mod;
    }
    printf("%lld\n",ans);
    return 0;
} 
每日一题 文章被收录于专栏

每题一题题目

全部评论

相关推荐

想干测开的tomca...:让我来压力你!!!: 这份简历看着“技术词堆得满”,实则是“虚胖没干货”,槽点一抓一大把: 1. **项目描述是“技术名词报菜名”,没半分自己的实际价值** 不管是IntelliDoc还是人人探店,全是堆Redis、Elasticsearch、RAG这些时髦词,但你到底干了啥?“基于Redis Bitmap管理分片”是你写了核心逻辑还是只调用了API?“QPS提升至1500”是你独立压测优化的,还是团队成果你蹭着写?全程没“我负责XX模块”“解决了XX具体问题”,纯把技术文档里的术语扒下来凑字数,看着像“知道名词但没实际动手”的实习生抄的。 2. **短项目塞满超纲技术点,可信度直接***** IntelliDoc就干了5个月,又是RAG又是大模型流式响应又是RBAC权限,这堆活儿正经团队分工干都得小半年,你一个后端开发5个月能吃透这么多?明显是把能想到的技术全往里面塞,生怕别人知道你实际只做了个文件上传——这种“技术堆砌式造假”,面试官一眼就能看出水分。 3. **技能栏是“模糊词混子集合”,没半点硬核度** “熟悉HashMap底层”“了解JVM内存模型”——“熟悉”是能手写扩容逻辑?“了解”是能排查GC问题?全是模棱两可的词,既没对应项目里的实践,也没体现深度,等于白写;项目里用了Elasticsearch的KNN检索,技能栏里提都没提具体掌握程度,明显是“用过但不懂”的硬凑。 4. **教育背景和自我评价全是“无效信息垃圾”** GPA前10%这么好的牌,只列“Java程序设计”这种基础课,分布式、微服务这些后端核心课提都不提,白瞎了专业优势;自我评价那堆“积极认真、细心负责”,是从招聘网站抄的模板吧?没有任何和项目挂钩的具体事例,比如“解决过XX bug”“优化过XX性能”,纯废话,看完等于没看。 总结:这简历是“技术名词缝合怪+自我感动式凑数”,看着像“背了后端技术栈名词的应届生”,实则没干货、没重点、没可信度——面试官扫30秒就会丢一边,因为连“你能干嘛”都没说清楚。
点赞 评论 收藏
分享
10-29 18:20
济南大学 Java
用微笑面对困难:他不是人事吗,怎么净特么不干人事
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务