企业官网建设流程全解析

P11855 [CSP-J 2022 山东] 部署

题目背景

受疫情影响，山东省取消了 CSP-J 2022 认证活动，并于次年三月重新命题，在省内补办比赛。

题目描述

“万里羽书来未绝，五关烽火昼仍传。”

古时候没有现代信息化战争的技术，只能靠烽火传信和将军运筹帷幄的调兵遣将来取得战争的优势。

为了使消耗最低，现在 A 国已经在nnn个城市之间建好了道路和行军部署渠道，使得这nnn个城市都能互相到达且不存在环（即构成以111号城市为根节点的树型结构）。每个城市都驻扎了一定数量的兵力。

为了清晰的描述问题，我们给这nnn个城市进行111到nnn的编号，且111号城市为树的根节点（数据保证：构成以111号城市为根节点的一棵树）。初始时，第iii座城市拥有初始兵力aia_{i}ai​。

现在为测试战争部署速度，将军进行了mmm次测试，每次测试可能为以下两种命令的某一种：

1 x y（三个数间均用 1 个空格分开）：向xxx号城市和以它为根的子树中的所有城市全部增兵yyy的数量。

2 x y（三个数间均用 1 个空格分开）：向xxx号城市和与它直接相连（含父结点和子结点）的城市全部增兵yyy的数量。

mmm条命令发布出去后，将军喊来参谋，进行了qqq次询问，每次询问第xxx座城市的最终兵力情况。
该参谋就是小虾米，他又向你求助了，请你帮助他解决问题（qqq次询问的结果）。

输入格式

第一行一个正整数nnn表示城市数量。

第二行一共nnn个正整数a1,a2,…ana_{1},a_{2},\dots a_{n}a1​,a2​,…an​表示每座城市的初始兵力。

接下来n−1n-1n−1行，每行两个整数x,yx,yx,y，表示xxx和yyy城市之间有直接相连的道路。

接下来一行一个正整数mmm，表示mmm次命令。

接下来mmm行，每行三个正整数p,x,yp,x,yp,x,y表示两种命令其中一种，其中p=1p=1p=1时表示第一种命令，p=2p=2p=2时表示第二种命令。

接下来一行一个正整数qqq，表示qqq次询问。

接下来qqq行，每行一个正整数xxx，表示询问编号为xxx的城市最后的兵力值。

输出格式

一共qqq行，每行一个正整数分别对应于每次询问的答案。

输入输出样例 #1

输入 #1

5 1 2 3 4 5 1 2 1 3 2 4 3 5 4 1 1 2 2 2 3 1 3 3 2 5 1 4 1 2 3 4

输出 #1

6 7 9 9

输入输出样例 #2

输入 #2

4 1 1 1 1 1 2 1 3 1 4 1 1 1 1 2 1 2

输出 #2

2 2

说明/提示

数据范围

对于30%30\%30%的数据，1≤n≤1000,1≤m≤10001\le n\le1000,1\le m\le10001≤n≤1000,1≤m≤1000；

对于60%60\%60%的数据，1≤n≤105,1≤m≤105,1≤q≤1051\le n\le10^{5},1\le m\le10^{5},1\le q\le10^{5}1≤n≤105,1≤m≤105,1≤q≤105；

其中10%10\%10%的数据树是一条链，另外10%10\%10%的数据只有111操作，另外10%10\%10%的数据只有222操作。

对于100%100\%100%的数据，数据保证给定的城市和道路能形成树，且111号城市为根节点。1≤n≤106,1≤m≤2×106,1≤q≤106,1≤ai≤109,1≤x≤n,1≤y≤101\le n\le10^{6},1\le m\le2\times10^{6},1\le q\le10^{6},1\le a_{i}\le10^{9},1\le x\le n,1\le y\le101≤n≤106,1≤m≤2×106,1≤q≤106,1≤ai​≤109,1≤x≤n,1≤y≤10。

2025-06-26 增加 Hack 一组

C++实现

#include<bits/stdc++.h>#definelllonglongusingnamespacestd;ll n,m,q,u,v,op,x,y,a[1000010],tag1[1000010],tag2[1000010],fa[1000010];vector<ll>g[1000010];voidchange(ll now){for(inti=0;i<g[now].size();i++){if(g[now][i]!=fa[now]){fa[g[now][i]]=now;change(g[now][i]);}}}voidpushdown(ll now){a[now]+=tag1[now];a[now]+=tag2[now];for(inti=0;i<g[now].size();i++){a[g[now][i]]+=tag2[now];if(g[now][i]!=fa[now]){tag1[g[now][i]]+=tag1[now];pushdown(g[now][i]);}}}intmain(){cin>>n;for(inti=0;i<n;i++){cin>>a[i];}for(inti=0;i<n-1;i++){cin>>u>>v;u--;v--;g[u].push_back(v);g[v].push_back(u);}fa[0]=0;change(0);cin>>m;while(m--){cin>>op>>x>>y;if(op==1)tag1[x-1]+=y;elsetag2[x-1]+=y;}pushdown(0);cin>>q;while(q--){cin>>x;cout<<a[x-1]<<endl;}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容