口碑好的做pc端网站,公司做个网站好还是做公众号好,wordpress外链图片自动,嘉兴网站建设与管理专业Jamie and Tree[CF916E]
题意#xff1a;
有一棵n个点的树#xff0c;每个节点上有一个权值wi#xff0c;最开始根为1号点#xff0e;现在有3种 类型的操作#xff1a; • 1 root, 表示将根设为root. • 2 u v x, 设u, v的最近公共祖先为p, 将p的子树中的所有点的权值加…Jamie and Tree[CF916E]
题意
有一棵n个点的树每个节点上有一个权值wi最开始根为1号点现在有3种 类型的操作 • 1 root, 表示将根设为root. • 2 u v x, 设u, v的最近公共祖先为p, 将p的子树中的所有点的权值加上x. • 3 u, 查询u的子树中的所有点的权值和 对于每个3操作输出答案
题解
须知知识线段树树链剖分
如果真的换根太麻烦了所以我们每次只记录新根并看看新根在后续操作中会有什么影响如果在没有换根的情况下操作2很容易实现但是因为现在root已经发生改变所以我们需要特判。 lca1lcau,v lca2lca(root,v) lca3lca(root,u) lcamax(dep[lca1],dep[lca2],dep[lca3]) 我们要先记录lca1lca2lca3中dep最深的 如果root不在lca的子树里那直接在区间[l[lca],r[lca]]内更新x即可 如果root等于lca那么就是全树更新 如果root在lca的子树上先把整个树更新然后找到root到lca的路径与lca的儿子节点更新子树-x 相当于先全部x然后将不需要修改的部分再-x
if(rootlca1)tree.update(1,1,n,1,n,x);else if(dfn[rt]dfn[lca1]||dfn[rt]dfn[lca1]size[lca1]-1)tree.update(1,1,n,dfn[lca1],dfn[lca1]size[lca1]-1,x);else {lca1change(lca1);tree.update(1,1,n,1,n,x);tree.update(1,1,x,dfn[lca1],dfn[lca1]size[lca1]-1,-x);}对于操作三我们要判断root与v的关系如果root不在v的子树上那就正常操作sum(l[v],r[v]) 如果root就是v更新整个子树 但如果root在v的子树上那么其实和操作2的第三个情况类似先求所以树的权值然后减去不需要算的部分。这里不需要算的部分是root到lca的路径与lca的儿子节点X 为什么是这个点看着图仔细想想
if(urt)sumtree.query(1,1,n,1,n);
else if(dfn[rt]dfn[u]||dfn[rt]dfn[u]size[u]-1)sumtree.query(1,1,n,dfn[u],dfn[u]size[u]-1);
else {uchange(u);sumtree.query(1,1,n,1,n);sum-tree.query(1,1,n,dfn[u],dfn[u]size[u]-1);}代码
#includebits/stdc.h#define REP(i,a,b) for(int ia;ib;i)
typedef long long ll;
using namespace std;templatetypename Tvoid read(T x){T _0,mul1;char chgetchar();while(!isdigit(ch)){if(ch-)mul-1;chgetchar();}while(isdigit(ch))_(_1)(_3)(ch^0),chgetchar();x_*mul;
}const int maxn3e510;struct Segment_Tree{
#define mid ((lr)1)
#define lc (rt1)
#define rc (rt1|1)
#define lson lc,l,mid
#define rson rc,mid1,rll sum[maxn2],tag[maxn2];void pushdown(int rt,int l,int r){sum[lc]tag[rt]*(mid-l1);tag[lc]tag[rt];sum[rc]tag[rt]*(r-mid); tag[rc]tag[rt];tag[rt]0;}void update(int rt,int l,int r,int L,int R,ll x){if(Ll rR){sum[rt](r-l1)*x;tag[rt]x;return;}if(tag[rt])pushdown(rt,l,r);if(Lmid)update(lson,L,R,x);if(Rmid1)update(rson,L,R,x);sum[rt]sum[lc]sum[rc];}ll query(int rt,int l,int r,int L,int R){if(Ll rR)return sum[rt];ll ret0ll;if(tag[rt])pushdown(rt,l,r);if(Lmid)retquery(lson,L,R);if(Rmid1)retquery(rson,L,R);return ret;}
}T;int n,q,root,w[maxn],cnt;
int to[maxn1],last[maxn1],beg[maxn],cnte;
int fa[maxn],son[maxn],top[maxn],siz[maxn],dep[maxn],cnt_dfn,dfn[maxn];void add(int u,int v){last[cnte]beg[u];beg[u]cnte;to[cnte]v;
}void dfs1(int u,int f){fa[u]f;siz[u]1;dep[u]dep[f]1;for(int ibeg[u];i;ilast[i]){if(to[i]f)continue;dfs1(to[i],u);siz[u]siz[to[i]];if(siz[to[i]]siz[son[u]])son[u]to[i];}
}void dfs2(int u,int t){dfn[u]cnt_dfn;top[u]t;if(son[u])dfs2(son[u],t);for(int ibeg[u];i;ilast[i]){if(to[i]fa[u] || to[i]son[u])continue;dfs2(to[i],to[i]);}
}int find(int u,int v){while(top[u]!top[v]){cnt;if(dep[top[u]]dep[top[v]])swap(u,v);ufa[top[u]];}return dep[u]dep[v] ? u : v;
}int change(int u){int vroot;while(top[v]!top[u]){if(fa[top[v]]u)return top[v];vfa[top[v]];}return son[u];
}void init(){read(n); read(q);root1;REP(i,1,n)read(w[i]);REP(i,1,n-1){int u,v;read(u); read(v);add(u,v);add(v,u);}dfs1(1,0);dfs2(1,1);REP(i,1,n)T.update(1,1,n,dfn[i],dfn[i],w[i]);
}int main(){init();REP(i,1,q){int ty,u,v;ll x;read(ty);if(ty1){read(u);rootu;}else if(ty2){read(u); read(v); read(x);int lcafind(u,v),tmp;if(dep[tmpfind(u,root)]dep[lca])lcatmp;if(dep[tmpfind(v,root)]dep[lca])lcatmp;if(lcaroot)T.update(1,1,n,1,n,x);else if(dfn[root]dfn[lca] || dfn[root]dfn[lca]siz[lca]-1)T.update(1,1,n,dfn[lca],dfn[lca]siz[lca]-1,x);else{lcachange(lca);T.update(1,1,n,1,n,x);T.update(1,1,n,dfn[lca],dfn[lca]siz[lca]-1,-x);}}else{ll sum0ll;read(u);if(uroot)sumT.query(1,1,n,1,n);else if(dfn[root]dfn[u] || dfn[root]dfn[u]siz[u]-1)sumT.query(1,1,n,dfn[u],dfn[u]siz[u]-1);else{uchange(u);sumT.query(1,1,n,1,n);sum-T.query(1,1,n,dfn[u],dfn[u]siz[u]-1);}coutsumendl;}}return 0;
}
