1、树链剖分
树链剖分模板
#include#define ll long long#define INF 2147483647#define mem(i,j) memset(i,j,sizeof(i))#define F(i,j,n) for(register int i=j;i<=n;i++)#define md pusing namespace std;struct hahaha{ int from,to,nxt;}s[200010];int n,m,r,p,head[200010],cnt=0,pls[1000010];int v[100010],f[100010],son[100010];int dep[100010],top[100010],sz[100010];int id[1000010],vt[1000010],num=0;inline int read(){ int datta=0;char chchc=getchar();bool okoko=0; while(chchc<'0'||chchc>'9'){if(chchc=='-')okoko=1;chchc=getchar();} while(chchc>='0'&&chchc<='9'){datta=datta*10+chchc-'0';chchc=getchar();} if(okoko==1)return -datta; return datta;}inline void ins(int from,int to){ s[++cnt].from=from; s[cnt].to=to; s[cnt].nxt=head[from]; head[from]=cnt;}inline int dfs1(int from){ int tmp=0,tmx=0,ti=0; for(int i=head[from];i;i=s[i].nxt){ int to=s[i].to; if(to!=f[from]){ dep[to]=dep[from]+1; f[to]=from; tmp=dfs1(to); sz[from]+=tmp; if(tmp>tmx) tmx=tmp,ti=to; } } sz[from]++; son[from]=ti; return sz[from];}inline void dfs2(int from,int tp){ id[from]=++num,vt[num]=v[from]; if(son[from]) top[son[from]]=tp,dfs2(son[from],tp); for(int i=head[from];i;i=s[i].nxt){ int to=s[i].to; if(to!=f[from]&&to!=son[from]) top[to]=to,dfs2(to,to); }}struct Segment_Tree{ #define ls u<<1 #define rs u<<1|1 #define mid ((l+r)>>1) int tree[1000010]; void updata(int u){ tree[u]=(tree[ls]+tree[rs])%md; } void pushdown(int u,int l,int r){ if(!pls[u]) return ; pls[ls]+=pls[u]; pls[rs]+=pls[u]; tree[ls]+=(mid-l+1)*(pls[u]); tree[rs]+=(r-mid)*(pls[u]); pls[u]=0; } void build_tree(int u,int l,int r){ if(l==r){ tree[u]=vt[l]; return ; } build_tree(ls,l,mid); build_tree(rs,mid+1,r); updata(u); } void change(int u,int l,int r,int x,int y,int z){ if(x<=l&&r<=y){ pls[u]+=z; tree[u]+=(r-l+1)*z; return ; } pushdown(u,l,r); if(x<=mid) change(ls,l,mid,x,y,z); if(y>=mid+1) change(rs,mid+1,r,x,y,z); updata(u); } int ask(int u,int l,int r,int x,int y){ int res=0; if(x<=l&&r<=y) return tree[u]; pushdown(u,l,r);; if(x<=mid) res+=ask(ls,l,mid,x,y); if(y>=mid+1) res+=ask(rs,mid+1,r,x,y); return res; }}T;inline void cRange(int x,int y,int z){ while(top[x]!=top[y]){ if(dep[top[x]]