树

2023-09-08 02:35| 来源: 网络整理| 查看: 265

题目描述

小L非常喜欢树。最近，他发现了一棵有趣的树。这棵树有n个节点(1到n编号)，节点i有一个初始的权值ai。这棵树的根是节点1。这棵树有一个特殊的性质：当你给节点i的权值加 val 的时候，节点i的所有儿子的权值都会加 -val。注意当你给节点i的儿子的权值加 -val 时，节点i的这个儿子的所有儿子的权值都会加 -(-val)，以此类推。样例说明可以很好地帮助你理解这个性质。有2种操作：操作(a).“1 x val”表示给节点x的权值加val。操作(b).“2 x”输出节点x当前的权值。为了帮助小L更好地理解这棵树，你必须处理m个操作。

输入

第一行包含2个整数n和m。第二行包含n个整数a1，a2，…，an（1≤ai≤1000）。接下来的n-1行，每行两个整数u和v(1≤u接下来的m行，每行包含2种操作的一种。每个操作都保证1≤x≤n，1≤val≤1000。

输出

对于每个操作(b)，输出一个整数，表示节点x当前的权值。

输入样例 5 5 1 2 1 1 2 1 2 1 3 2 4 2 5 1 2 3 1 1 2 2 1 2 2 2 4 输出样例复制 3 3 0 说明

【输入输出样例说明】初始各个节点的权值依次为[1，2，1，1，2]。第一个操作给节点2的权值增加3，会给节点2的儿子4、5的权值增加-3。此时各个节点的权值变成[1，5，1，-2，-1]。第二个操作给节点1的权值增加2，会给节点1的儿子2、3的权值增加-2，然后会给节点2的儿子4、5的权值增加-(-2)。各个节点的权值变成[3，3，-1，0，1]。

【数据说明】对于50%的数据，1≤n≤2000，1≤m≤2000。对于100%的数据，1≤n≤100000，1≤m≤100000。

暴力80分思路

直接暴搜

#include #include #include using namespace std; int h[100025],F[100025]; int n,m,t,x,y,Operation; struct whw { int w,h; }wh[100025]; void hw(int x,int y) {wh[++t]=(whw){y,h[x]},h[x]=t;} void as(int k,int Num) { F[k]-=Num; for(int i=h[k];i;i=wh[i].h) as(wh[i].w,-Num); } int main() { scanf("%d%d",&n,&m); for(int i=1;i scanf("%d",&Operation); if(Operation==1) { scanf("%d%d",&x,&y); as(x,-y); } else { scanf("%d",&x); printf("%d\n",F[x]); } } return 0; }

【本文地址】

树

树

今日新闻

推荐新闻