找网站公司做网站的陷阱,找人做网站 网站定制开发,崇明注册公司,嘉定区 网站建设【题目来源】https://www.acwing.com/problem/content/2570/【题目描述】 给定一棵树#xff0c;树中包含 n 个节点#xff08;编号 1∼n#xff09;#xff0c;其中第 i 个节点的权值为 ai。 初始时#xff0c;1 号节点为树的根节点。 现在要对该树进行 m 次操作#xf…【题目来源】https://www.acwing.com/problem/content/2570/【题目描述】 给定一棵树树中包含 n 个节点编号 1∼n其中第 i 个节点的权值为 ai。 初始时1 号节点为树的根节点。 现在要对该树进行 m 次操作操作分为以下 4 种类型 ● 1 u v k修改路径上节点权值将节点 u 和节点 v 之间路径上的所有节点包括这两个节点的权值增加 k。 ● 2 u k修改子树上节点权值将以节点 u 为根的子树上的所有节点的权值增加 k。 ● 3 u v询问路径询问节点 u 和节点 v 之间路径上的所有节点包括这两个节点的权值和。 ● 4 u询问子树询问以节点 u 为根的子树上的所有节点的权值和。【输入格式】 第一行包含一个整数 n表示节点个数。 第二行包含 n 个整数其中第 i 个整数表示 ai。 接下来 n−1 行每行包含两个整数 x,y表示节点 x 和节点 y 之间存在一条边。 再一行包含一个整数 m表示操作次数。 接下来 m 行每行包含一个操作格式如题目所述。【输出格式】 对于每个操作 3 和操作 4输出一行一个整数表示答案。【数据范围】 1≤n,m≤10^5, 0≤ai,k≤10^5, 1≤u,v,x,y≤n【输入样例】 5 1 3 7 4 5 1 3 1 4 1 5 2 3 5 1 3 4 3 3 5 4 1 3 5 10 2 3 5 4 1【输出样例】 16 69【算法分析】 ● 树链剖分 1树链剖分的核心思想就是将树中任意一条路径拆分成 段的连续区间或重链。拆分后树的所有操作都可转化为区间操作且通常采用线段树进行维护。 2树链剖分的几个概念重儿子/轻儿子结点个数最多的子树的根结点称为当前结点的重儿子其他子结点称为当前结点的轻儿子。若当前结点存在多个结点个数相同的子树则任选一个子树的根结点作为当前结点的重儿子。故易知每个结点的重儿子是唯一的。重边/轻边重儿子与父结点之间的边称为重边。其他边称为轻边。重链重边构成的极大路径称为重链。DFS序深度优先遍历树的重儿子可保证树中各条重链结点的编号是连续的。此性质保证了树链剖分后各区间是连续的。 3将一条路径拆分为重链的过程类似于求最近公共祖先LCA。【算法代码】
#include bits/stdc.h
using namespace std;typedef long long LL;const int maxn1e55;
const int maxmmaxn1;
int val[maxn],e[maxm],ne[maxm],h[maxn],idx;//id[]:dfn sequence number of the node
//nv[]:point weight of each dfs sequence number
int id[maxn],nv[maxn],tot;//cnt[]:number of child nodes, top[]:vertex of heavy chain
//son[]:heavy son, fa[]:parent node
int dep[maxn],cnt[maxn],top[maxn],fa[maxn],son[maxn];int n,m;struct SegmentTree {int le,ri;LL sum,lazy;
} tr[maxn2];void add(int a,int b) {e[idx]b,ne[idx]h[a],h[a]idx;
}void dfs1(int u,int father,int depth) { //dfs1:pretreatmentdep[u]depth,fa[u]father,cnt[u]1;for(int ih[u]; i!-1; ine[i]) {int je[i];if(jfather) continue;dfs1(j,u,depth1);cnt[u]cnt[j];if(cnt[son[u]]cnt[j]) son[u]j; //heavy son}
}void dfs2(int u,int vx) { //dfs2:split, t:vertex of heavy chainid[u]tot,nv[tot]val[u],top[u]vx;if(!son[u]) return; //leaf nodedfs2(son[u], vx); //Heavy sons heavy chain splitfor(int ih[u]; i!-1; ine[i]) { //handle light sonint je[i];if(jfa[u] || json[u]) continue;dfs2(j,j); //The vertex of the light sons heavy chain is himself}
}/*------------ Content of segment tree ------------*/void pushup(int u) {tr[u].sumtr[u1].sumtr[u1|1].sum;
}void pushdown(int u) {auto rttr[u], Ltr[u1], Rtr[u1|1];if(rt.lazy) {L.sumrt.lazy*(L.ri-L.le1);L.lazyrt.lazy;R.sumrt.lazy*(R.ri-R.le1);R.lazyrt.lazy;rt.lazy0;}
}void build(int u,int le,int ri) {tr[u] {le,ri,nv[ri],0};if(leri) return;int midleri1;build(u1,le,mid), build(u1|1,mid1,ri);pushup(u);
}void update(int u,int le,int ri,int k) {if(letr[u].le ritr[u].ri) {tr[u].lazyk;tr[u].sumk*(tr[u].ri-tr[u].le1);return;}pushdown(u);int midtr[u].letr[u].ri1;if(lemid) update(u1,le,ri,k);if(rimid) update(u1|1,le,ri,k);pushup(u);
}LL query(int u,int le,int ri) {if(letr[u].le ritr[u].ri) return tr[u].sum;pushdown(u);int mid(tr[u].letr[u].ri)1;LL res0;if(lemid) resquery(u1,le,ri);if(rimid) resquery(u1|1,le,ri);return res;
}void update_path(int u,int v,int k) {while(top[u]!top[v]) { //Climb up to find the same heavy chainif(dep[top[u]]dep[top[v]]) swap(u,v);//Because of dfs order, the id of the upper node//must be smaller than that of the lower nodeupdate(1,id[top[u]],id[u],k);ufa[top[u]];}if(dep[u]dep[v]) swap(u,v);//In the same heavy chain, the remaining intervals are processedupdate(1,id[v],id[u],k);
}LL query_path(int u,int v) {LL res0;while(top[u]!top[v]) { //Climb up to find the same heavy chainif(dep[top[u]]dep[top[v]]) swap(u,v);resquery(1,id[top[u]],id[u]);ufa[top[u]];}if(dep[u]dep[v]) swap(u,v);//In the same heavy chain, the remaining intervals are processedresquery(1,id[v],id[u]);return res;
}void update_tree(int u,int k) { //Add k to all the subtrees//Because of the order of dfs, the interval can be found directly//by the number of subtree nodesupdate(1,id[u],id[u]cnt[u]-1,k);
}LL query_tree(int u) {//Because of the order of dfs, the interval can be found directly//by the number of subtree nodesreturn query(1,id[u],id[u]cnt[u]-1);
}int main() {scanf(%d,n);memset(h,-1,sizeof h);for(int i1; in; i) scanf(%d,val[i]);for(int i1; in; i) {int a,b;scanf(%d %d,a,b);add(a,b),add(b,a);}dfs1(1,-1,1);dfs2(1,1);build(1,1,n);scanf(%d,m);while(m--) {int op,u,v,k;scanf(%d%d,op,u);if(op1) {scanf(%d%d,v,k);update_path(u,v,k);} else if(op2) {scanf(%d,k);update_tree(u,k);} else if(op3) {scanf(%d,v);printf(%lld\n,query_path(u,v));} else printf(%lld\n,query_tree(u));}return 0;
}/*
in:
5
1 3 7 4 5
1 3
1 4
1 5
2 3
5
1 3 4 3
3 5 4
1 3 5 10
2 3 5
4 1out:
16
69
*/【参考文献】https://www.acwing.com/solution/content/62664/https://www.acwing.com/problem/content/video/2570/https://blog.csdn.net/qq_46105170/article/details/125497358
