一般网站的后台怎么做的,国外网站注册,福州网站制作网站,婚礼策划网站模板【题目描述】 有一棵点数为N的树#xff0c;以点1为根#xff0c;且树点有边权。然后有M个操作#xff0c;分为三种#xff1a; 操作1#xff1a;把某个节点x的点权增加a。 操作2#xff1a;把某个节点x为根的子树中所有点的点权都增加a。 操作3#xff1a;询问某个节点…【题目描述】 有一棵点数为N的树以点1为根且树点有边权。然后有M个操作分为三种 操作1把某个节点x的点权增加a。 操作2把某个节点x为根的子树中所有点的点权都增加a。 操作3询问某个节点x到根的路径中所有点的点权和。 【输入格式】 第一行两个整数N,M表示点数和操作数。 接下来一行N个整数表示树中节点的初始权值。 接下来N-1行每行两个正整数fr,to表示该树中存在一条边(fr,to)。 再接下来M行每行分别表示一次操作。其中第一个数表示该操作的种类1~3之后接这个操作的参数x或者x a。 【输出格式】 对于每个询问操作输出该询问的答案。答案之间用换行隔开。 【样例输入】 5 5 1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3 【样例输出】 6 9 13 【提示】 对于30%的数据N,M1000 对于50%的数据N,M100000且数据随机。 对于100%的数据N,M100000且所有输入数据的绝对值都不会超过10^6。 1 #includeiostream2 #includecstdio3 #includecstdlib4 #includecstring5 #includecmath6 #includealgorithm7 #includevector8 #includequeue9 using namespace std;10 typedef long long LL;11 const LL maxn100010;12 inline LL read(){13 LL x0,f1;char chgetchar();14 while(ch0||ch9){if(ch-)f-1;chgetchar();}15 while(ch0ch9){xx*10ch-0;chgetchar();}16 return x*f;17 }18 vectorLL to[maxn];19 LL N,M;20 LL a[maxn];21 LL dep[maxn],fa[maxn],son[maxn],top[maxn],siz[maxn],id[maxn];22 LL val[maxn];23 LL num;24 inline void dfs1(LL rt,LL fath,LL deep){25 dep[rt]deep; siz[rt]1; fa[rt]fath;26 for(LL i0;ito[rt].size();i){27 LL yto[rt][i];28 if(y!fa[rt]){29 dfs1(y,rt,deep1);30 siz[rt]siz[y];31 if(siz[son[rt]]siz[y]) son[rt]y;32 }33 }34 }35 inline void dfs2(LL rt,LL tp){36 top[rt]tp; id[rt]num;37 if(son[rt]!0) dfs2(son[rt],tp);38 for(LL i0;ito[rt].size();i){39 LL yto[rt][i];40 if(y!fa[rt]y!son[rt]){41 dfs2(y,y);42 }43 }44 }45 struct node{46 LL l,r;47 LL sum,lazy;48 }tree[maxn*8];49 inline void build(LL rt,LL l,LL r){50 tree[rt].ll; tree[rt].rr;51 if(lr){52 tree[rt].sumval[l];53 tree[rt].lazy0;54 return ;55 }56 LL mid(lr)1;57 build(rt1,l,mid); build(rt1|1,mid1,r);58 tree[rt].sumtree[rt1].sumtree[rt1|1].sum;59 }60 inline void update_son(LL rt){61 LL dtree[rt].lazy;62 if(d!0){63 tree[rt1].sum(tree[rt1].r-tree[rt1].l1)*d;64 tree[rt1|1].sum(tree[rt1|1].r-tree[rt1|1].l1)*d;65 tree[rt1].lazyd; tree[rt1|1].lazyd;66 tree[rt].lazy0;67 }68 }69 inline void change(LL rt,LL l,LL r,LL delta){70 if(ltree[rt].ltree[rt].rr){71 tree[rt].sum(tree[rt].r-tree[rt].l1)*delta;72 tree[rt].lazydelta;73 return ;74 }75 update_son(rt);76 LL mid(tree[rt].ltree[rt].r)1;77 if(lmid) change(rt1,l,r,delta);78 if(mid1r) change(rt1|1,l,r,delta);79 tree[rt].sumtree[rt1].sumtree[rt1|1].sum;80 }81 inline LL query(LL rt,LL l,LL r){82 if(ltree[rt].ltree[rt].rr){83 return tree[rt].sum;84 }85 update_son(rt);86 LL ans0;87 LL mid(tree[rt].ltree[rt].r)1;88 if(lmid) ansquery(rt1,l,r);89 if(mid1r) ansquery(rt1|1,l,r);90 return ans;91 }92 inline void ASK(LL x){93 LL tptop[x],ans0;94 while(x!0tp!0){95 ansquery(1,id[tp],id[x]);96 xfa[tp]; tptop[x];97 }98 printf(%lld\n,ans);99 }
100 int main(){
101 Nread(); Mread();
102 for(LL i1;iN;i) a[i]read();
103 for(LL i1,u,v;iN-1;i){
104 uread(); vread();
105 to[u].push_back(v); to[v].push_back(u);
106 }
107 dis[1]a[1];
108 dfs1(1,0,1); dfs2(1,1);
109 for(LL i1;iN;i) val[id[i]]a[i];
110 build(1,1,num);
111 for(LL i1,kin;iM;i){
112 kinread();
113 if(kin1){
114 LL xread(),dread();
115 change(1,id[x],id[x],d);
116 }
117 else if(kin2){
118 LL xread(),dread();
119 change(1,id[x],id[x]siz[x]-1,d);
120 }
121 else if(kin3){
122 LL xread();
123 ASK(x);
124 }
125 }
126 return 0;
127 } 转载于:https://www.cnblogs.com/CXCXCXC/p/5022114.html
