当前位置: 开发笔记 > 程序员 > 正文

牛客练习赛6B点权和树点权和

作者：Smile--麦芽 | 来源：互联网 | 2023-05-18 01:15

https:www.nowcoder.comacmcontest26B考虑每次修改的贡献考虑这次操作x造成的影响：x对自己的贡献：x的

https://www.nowcoder.com/acm/contest/26/B

考虑每次修改的贡献

考虑这次操作x造成的影响：

x对自己的贡献：

x的节点值会加上deg[x]+1，deg为度数

x对上方的贡献：

x的父亲节点的值会加上2

x的父亲的父亲节点的值会加上1

x的父亲节点的儿子值会加上1

x对下方的贡献：

x的儿子节点值会加上2

x的儿子的儿子节点值会加上1

///                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
///             __.'              ~.   .~              `.__
///           .'//                  \./                  \\`.
///        .'//                     |                     \\`.
///       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \\`.
///     .'//.-"                 `-.  |  .-'                 "-.\\`.
///   .'//______.============-..   \ | /   ..-============.______\\`.
/// .'______________________________\|/______________________________`.
#pragma GCC optimize(2)
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define pi acos(-1)
#define s_1(x) scanf("%d",&x)
#define s_2(x,y) scanf("%d%d",&x,&y)
#define s_3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define s_4(x,y,z,X) scanf("%d%d%d%d",&x,&y,&z,&X)
#define S_1(x) scan_d(x)
#define S_2(x,y) scan_d(x),scan_d(y)
#define S_3(x,y,z) scan_d(x),scan_d(y),scan_d(z)
#define PI acos(-1)
#define endl '\n'
#define srand() srand(time(0));
#define me(x,y) memset(x,y,sizeof(x));
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)
#define close() ios::sync_with_stdio(0); cin.tie(0);
#define FOR(x,n,i) for(int i=x;i<=n;i++)
#define FOr(x,n,i) for(int i=x;i=x;i--)
#define fOr(n,x,i) for(int i=n;i>x;i--)
#define W while
#define sgn(x) ((x) <0 ? -1 : (x) > 0)
#define bug printf("***********\n");
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
typedef long long LL;
typedef pair  ii;
const int INF=~0U>>1;
const LL LINF=0x3f3f3f3f3f3f3f3fLL;
const int dx[]={-1,0,1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,-1,1,-1,1};
const int maxn=1e5+10;
const int maxx=1e6+10;
const double EPS=1e-8;
const double eps=1e-8;
const int mod=19260817;
templateinline T min(T a,T b,T c) { return min(min(a,b),c);}
templateinline T max(T a,T b,T c) { return max(max(a,b),c);}
templateinline T min(T a,T b,T c,T d) { return min(min(a,b),min(c,d));}
templateinline T max(T a,T b,T c,T d) { return max(max(a,b),max(c,d));}
template 
inline bool scan_d(T &ret){char c;int sgn;if (c = getchar(), c == EOF){return 0;}
while (c != '-' && (c <'0' || c > '9')){c = getchar();}sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0' && c <= '9'){ret = ret * 10 + (c - '0');}ret *= sgn;return 1;}

inline bool scan_lf(double &num){char in;double Dec=0.1;bool IsN=false,IsD=false;in=getchar();if(in==EOF) return false;
while(in!='-'&&in!='.'&&(in<'0'||in>'9'))in=getchar();if(in=='-'){IsN=true;num=0;}else if(in=='.'){IsD=true;num=0;}
else num=in-'0';if(!IsD){while(in=getchar(),in>='0'&&in<='9'){num*=10;num+=in-'0';}}
if(in!='.'){if(IsN) num=-num;return true;}else{while(in=getchar(),in>='0'&&in<='9'){num+=Dec*(in-'0');Dec*=0.1;}}
if(IsN) num=-num;return true;}

void Out(LL a){if(a <0) { putchar('-'); a = -a; }if(a >= 10) Out(a / 10);putchar(a % 10 + '0');}
void print(LL a){ Out(a),puts("");}
//freopen( "in.txt" , "r" , stdin );
//freopen( "data.txt" , "w" , stdout );
//cerr <<"run time is " <

https

推荐阅读

安全
eBPF和WebAssembly：云原生VM的比较及应用领域

本文比较了eBPF和WebAssembly作为云原生VM的特点和应用领域。eBPF作为运行在Linux内核中的轻量级代码执行沙箱，适用于网络或安全相关的任务；而WebAssembly作为图灵完备的语言，在商业应用中具有优势。同时，介绍了WebAssembly在Linux内核中运行的尝试以及基于LLVM的云原生WebAssembly编译器WasmEdge Runtime的案例，展示了WebAssembly作为原生应用程序的潜力。 ... [详细]

蜡笔小新 2023-12-14 21:27:37
安全
Codeforces 1294A题解：Collecting Coins整除+不整除问题解析

本文为Codeforces 1294A题目的解析，主要讨论了Collecting Coins整除+不整除问题。文章详细介绍了题目的背景和要求，并给出了解题思路和代码实现。同时提供了在线测评地址和相关参考链接。 ... [详细]

蜡笔小新 2023-12-14 21:14:58
安全
linux查看目录权限命令,linux修改文件目录权限

Linuxchmod目录权限命令图文详解在Linux文件系统模型中，每个文件都有一组9个权限位用来控制谁能够读写和执行该文件的内容。对于目录来说，执行位的作用是控制能否进入或者通过 ... [详细]

蜡笔小新 2023-12-14 19:06:22
安全
Skywalking系列博客1安装单机版 Skywalking的快速安装方法

本文介绍了如何快速安装单机版的Skywalking，包括下载、环境需求和端口检查等步骤。同时提供了百度盘下载地址和查询端口是否被占用的命令。 ... [详细]

蜡笔小新 2023-12-14 19:05:47
安全
解决Docker中volume的权限问题的方法

在Docker中，将主机目录挂载到容器中作为volume使用时，常常会遇到文件权限问题。这是因为容器内外的UID不同所导致的。本文介绍了解决这个问题的方法，包括使用gosu和suexec工具以及在Dockerfile中配置volume的权限。通过这些方法，可以避免在使用Docker时出现无写权限的情况。 ... [详细]

蜡笔小新 2023-12-14 18:48:02
安全
Lodop中特殊符号打印设计和预览样式不同的问题解析

本文主要解析了在Lodop中使用特殊符号打印设计和预览样式不同的问题。由于调用的本机ie引擎版本可能不同，导致在不同浏览器下样式解析不同。同时，未指定文字字体和样式设置也会导致打印设计和预览的差异。文章提出了通过指定具体字体和样式来解决问题的方法，并强调了以打印预览和虚拟打印机测试为准。 ... [详细]

蜡笔小新 2023-12-14 18:29:32
安全
安装mysqlclient失败解决办法

本文介绍了在MAC系统中，使用django使用mysql数据库报错的解决办法。通过源码安装mysqlclient或将mysql_config添加到系统环境变量中，可以解决安装mysqlclient失败的问题。同时，还介绍了查看mysql安装路径和使配置文件生效的方法。 ... [详细]

蜡笔小新 2023-12-14 18:24:10
安全
Final关键字的含义及用法详解

本文详细介绍了Java中final关键字的含义和用法。final关键字可以修饰非抽象类、非抽象类成员方法和变量。final类不能被继承，final类中的方法默认是final的。final方法不能被子类的方法覆盖，但可以被继承。final成员变量表示常量，只能被赋值一次，赋值后值不再改变。文章还讨论了final类和final方法的应用场景，以及使用final方法的两个原因：锁定方法防止修改和提高执行效率。 ... [详细]

蜡笔小新 2023-12-14 18:07:46
安全
gcdexgcd斐蜀定理的求解方法及应用

本文介绍了求解gcdexgcd斐蜀定理的迭代法和递归法，并解释了exgcd的概念和应用。exgcd是指对于不完全为0的非负整数a和b，gcd(a,b)表示a和b的最大公约数，必然存在整数对x和y，使得gcd(a,b)=ax+by。此外，本文还给出了相应的代码示例。 ... [详细]

蜡笔小新 2023-12-14 17:48:30
安全
Python3中选择文件对话框的格式打开和保存图片

本文介绍了在Python3中如何使用选择文件对话框的格式打开和保存图片的方法。通过使用tkinter库中的filedialog模块的asksaveasfilename和askopenfilename函数，可以方便地选择要打开或保存的图片文件，并进行相关操作。具体的代码示例和操作步骤也被提供。 ... [详细]

蜡笔小新 2023-12-14 17:46:55
安全
EPICS Archiver Appliance存储waveform记录的尝试及资源需求分析

本文介绍了EPICS Archiver Appliance存储waveform记录的尝试过程，并分析了其所需的资源容量。通过解决错误提示和调整内存大小，成功存储了波形数据。然后，讨论了储存环逐束团信号的意义，以及通过记录多圈的束团信号进行参数分析的可能性。波形数据的存储需求巨大，每天需要近250G，一年需要90T。然而，储存环逐束团信号具有重要意义，可以揭示出每个束团的纵向振荡频率和模式。 ... [详细]

蜡笔小新 2023-12-14 17:43:56
cas
Android开发笔记：使用Picasso加载网络图片等比例缩放

在Android开发中，使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法，并提供了具体的代码实现。通过获取图片的宽高，计算目标宽度和高度，并创建新图实现等比例缩放。 ... [详细]

蜡笔小新 2023-12-14 17:34:00
cas
Android 新闻App的本地服务器搭建教程

本文介绍了在开发Android新闻App时，搭建本地服务器的步骤。通过使用XAMPP软件，可以一键式搭建起开发环境，包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表，并设置相应的属性。最后，给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]

蜡笔小新 2023-12-14 17:15:19
架构
云原生边缘计算之KubeEdge简介及功能特点

本文介绍了云原生边缘计算中的KubeEdge系统，该系统是一个开源系统，用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建，并为网络应用程序提供基础架构支持。同时，KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外，KubeEdge还支持跨平台工作，在私有、公共和混合云中都可以运行。同时，KubeEdge还提供数据管理和数据分析管道引擎的支持。最后，本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]

蜡笔小新 2023-12-14 16:49:01
架构
Microsoft Office for Mac最新版本安装教程，亲测可用！

本文介绍了Microsoft Office for Mac最新版本的安装教程，经过亲测可用。Office工具是办公必备的工具，它为用户和企业设计，可以利用功能强大的Outlook处理电子邮件、日历和通讯录事宜。安装包包括Word、Excel、PPT、OneNote和Outlook。阅读本文可以了解如何下载并安装Office，以及安装过程中的注意事项。安装完毕后，可以正常使用Office中的Word等功能。 ... [详细]

蜡笔小新 2023-12-14 16:36:04

Smile--麦芽

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章