题意：给予一颗树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和（与点x树上距离<=1的所有点点权之和）.如果是第i次操作，这次操作结果为ans,则这个结果的值加上i * ans，结果模19260817。 思路：设数组f1[]记录该点本身修改
展开全文
点权和 题目地址： https://ac.nowcoder.com/acm/problem/14393 基本思路: 这题的题意好像说的不是很明白，其实意思应该是第次操作先将与x树上距离<=1的点点权加一后，再将这些与x树上距离<=1的点的点权之和作为这次操作的结果乘以记录进最终结
展开全文
题解： 我试图去遍历邻接表（以为是水题），结果T飞了呀——m1e7，随便出点数据就可以卡了。 看一下正解： 用一个数组表示，当前这个点操作了几次，那么就如上图所示，绿色的点操作x次对此次操作的贡献即为2x，蓝色的点为1x。 很显然x的操作次数的贡献为：x的度数+1。 所以显然需要维护邻接点，但是
展开全文
感谢sunsetcolors大佬的博客，提供思路 首先题意需要仔细看，大致就是，给你一棵树，开始每个点权都是0，m次操作，每次操作会把这个点在树上距离小于等于1的点权都加1. 并且把这个点权和距离小于等于1的点权都加起来为k， ans=k*i。 i表示每次操作的编号 分析: 由于m=1000000很
展开全文
牛客——点权和 （4个月前好像见过这个题？） 思路： 考虑每次修改后对答案的贡献，对于一个点来说，考虑这个点会影响到哪些点。 考虑只进行一次更新的情况：首先，就是本身，本身的节点值对答案的贡献是度数+1，因为本身的点权会更新，邻接点也会更新；再者，就是他的父节点，父节点对答案的贡献是2，因为在这个过
展开全文
这题的标签是倍增。。。这真的算倍增的吗。
由于题中所给是父亲节点，那么可以想办法将儿子节点带来的贡献转化成x作为父亲节点时儿子所带来的贡献。这样通过记录每一个点作为自身、父亲、爷爷。所接受的影响。
三个关键数组：
tag[x]：x节点改变对自身的改变。
ftag[x]：x节点
展开全文
题目描述给你一棵树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和.输入描述:第一行两个数n和m第二行n-1个数，第i个数fa[i + 1]表示i + 1点的父亲编号，保证fa[i + 1]<i + 1第三行m个数，每个数x依次表示这次操作的
展开全文
题目链接 题意： 题解： AC代码 /*
Author : zzugzx
Lang : C++
Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#
展开全文
题意 题意就是给出一棵树，树上所有的节点的权值都是0，现在对一个点进行操作，这个点周围所有的（距离小于等于1 ）的点权值都加一，每操作一次，ans加上这个点距离小于等于一的所有点的权值和乘以i（i表示第几次操作),最后输出总的值。 解析 参考了隔壁大佬的博客，大佬博客,大佬的博客实在是难懂，看懂了之
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
