佛山网站如何制作,淘宝网店开店网站建设,网站空间为什么都比数据库大,河间建设网站重链剖分 P3384 【模板】轻重链剖分/树链剖分 $ / $ 模板代码#xff1a; 注意#xff1a; 如果有 \(0\) 号节点#xff0c;并默认重儿子是零号节点#xff0c;复杂度会退化为 \(O(n^2)\) 。原因#xff1a; 代码第一次遍历默认重儿子是0#xff0c;所以无法保证每次找到… 重链剖分 P3384 【模板】轻重链剖分/树链剖分 $ / $ 模板代码 注意 如果有 \(0\) 号节点并默认重儿子是零号节点复杂度会退化为 \(O(n^2)\) 。原因 代码第一次遍历默认重儿子是0所以无法保证每次找到重儿子。如果重儿子的节点数小于根节点那么重儿子不会被记录。 而在第二次遍历中因为应该被找到的重儿子没被找到所以少了重边。 由于少了很多重链本来可以一次跳到重链顶的转移必须沿着轻链条很多次时间复杂度就上去了由 \(O(n \log n)\) 退化为 \(O(n^2)\) 解决方法将每一个节点编号都加一 。 #includebits/stdc.h
using namespace std;
#define Maxn 100005
typedef long long ll;
inline int rd()
{int x0;char ch,t0;while(!isdigit(ch getchar())) t|ch-;while(isdigit(ch)) xx*10(ch^48),chgetchar();return xt?-x:x;
}
int n,m,root,mod,tot1,N;
int val[Maxn],fa[Maxn],siz[Maxn],Bigson[Maxn];
int tp[Maxn],dep[Maxn],dfnl[Maxn],dfnr[Maxn],reg[Maxn]; // reg dfn是线段树上的节点号与所对应的真实节点号不同
int hea[Maxn],ver[Maxn*2],nex[Maxn*2];
struct TREE { int sum,laz; }tree[Maxn2];
void add_edge(int x,int y) { ver[tot]y,nex[tot]hea[x],hea[x]tot; }
void dfs1(int x)
{siz[x]1;for(int ihea[x];i;inex[i]){if(ver[i]fa[x]) continue;dep[ver[i]]dep[x]1,fa[ver[i]]x;dfs1(ver[i]);siz[x]siz[ver[i]];if(siz[ver[i]]siz[Bigson[x]]) Bigson[x]ver[i];}
}
void dfs2(int x,int T)
{tp[x]T,dfnl[x]N,reg[N]x;if(Bigson[x]) dfs2(Bigson[x],T);for(int ihea[x];i;inex[i]){if(ver[i]fa[x] || ver[i]Bigson[x]) continue;dfs2(ver[i],ver[i]);}dfnr[x]N;
}
void pushdown(int p,int nl,int nr)
{if(tree[p].laz){int mid(nlnr)1;tree[p1].sum(tree[p1].sumtree[p].laz*(mid-nl1))%mod;tree[p1|1].sum(tree[p1|1].sumtree[p].laz*(nr-mid))%mod;tree[p1].laz(tree[p1].laztree[p].laz)%mod;tree[p1|1].laz(tree[p1|1].laztree[p].laz)%mod;tree[p].laz0;}
}
void build(int p,int nl,int nr)
{if(nlnr) { tree[p].sumval[reg[nl]]; return; }int mid(nlnr)1;build(p1,nl,mid),build(p1|1,mid1,nr);tree[p].sum(tree[p1].sumtree[p1|1].sum)%mod;
}
void add(int p,int nl,int nr,int l,int r,int k)
{if(nll nrr){tree[p].sum(tree[p].sumk*(nr-nl1))%mod;tree[p].lazk;return;}pushdown(p,nl,nr);int mid(nlnr)1;if(midl) add(p1,nl,mid,l,r,k);if(midr) add(p1|1,mid1,nr,l,r,k);tree[p].sum(tree[p1].sumtree[p1|1].sum)%mod;
}
int query(int p,int nl,int nr,int l,int r)
{if(nll nrr) return tree[p].sum;pushdown(p,nl,nr);int mid(nlnr)1,ret0;if(midl) retquery(p1,nl,mid,l,r);if(midr) retquery(p1|1,mid1,nr,l,r);tree[p].sum(tree[p1].sumtree[p1|1].sum)%mod;return ret%mod;
}
void add_path(int x,int y,int k) // 注意这道题的权重在 点 上
{while(tp[x]!tp[y]){if(dep[tp[x]]dep[tp[y]]) swap(x,y);add(1,1,n,dfnl[tp[x]],dfnl[x],k);xfa[tp[x]];}if(dep[x]dep[y]) swap(x,y);add(1,1,n,dfnl[y],dfnl[x],k);
}
int query_path(int x,int y)
{int ret0;while(tp[x]!tp[y]){if(dep[tp[x]]dep[tp[y]]) swap(x,y);ret(retquery(1,1,n,dfnl[tp[x]],dfnl[x]))%mod;xfa[tp[x]];}if(dep[x]dep[y]) swap(x,y);ret(retquery(1,1,n,dfnl[y],dfnl[x]))%mod;return ret;
}
int main()
{//freopen(.in,r,stdin);//freopen(.out,w,stdout);nrd(),mrd(),rootrd(),modrd();for(int i1;in;i) val[i]rd();for(int i1,u,v;in;i) urd(),vrd(),add_edge(u,v),add_edge(v,u);dfs1(root),dfs2(root,root),build(1,1,n);for(int i1,opt,x,y,z;im;i){optrd();if(opt1) xrd(),yrd(),zrd()%mod,add_path(x,y,z);else if(opt2) xrd(),yrd(),printf(%d\n,query_path(x,y));else if(opt3) xrd(),zrd(),add(1,1,n,dfnl[x],dfnr[x],z);else xrd(),printf(%d\n,query(1,1,n,dfnl[x],dfnr[x]));}//fclose(stdin);//fclose(stdout);return 0;
}
