2014年初中竞赛试题(南海) 树

2014年初中竞赛试题(南海) 树

题目

解题思路

正解：深度优先搜索+树状数组/线段树

歪解：递归+一个类似于线段树的思想

代码【歪解】

#include<cstdio>
using namespace std; 
int n,m,wt,w[100001],fa[100001],li[100001]; int u,v;//li记录i节点要"加"的值(但并不加,在递归时才带着走)int update(int x,int y)//y是题目中的奇偶
{ return !x?0:update(fa[x],-y)+li[x]*y; }int main()
{scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)scanf("%d",&w[i]); for (int i=1;i<=n-1;i++)scanf("%d%d",&u,&v),fa[v]=u; for (int i=1;i<=m;i++){scanf("%d",&wt); int q,e; if (wt==2) scanf("%d",&q),printf("%dn",w[q]+update(q,1));else scanf("%d%d",&q,&e),li[q]+=e;}
}