关键词：
【题解】
树链剖分模板题。。
#include<cstdio>
#include<algorithm>
#include<queue>
#define N 500010
#define rg register
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((a[u].l+a[u].r)>>1)
#define len(x) (a[x].r-a[x].l+1)
using namespace std;
int n,m,rt,num,x,y,z,fa[N],dfn[N],dep[N],size[N],heavy[N],top[N];
vector<int>son[N];
struct tree
int l,r;
long long sum,del;
a[N];
inline int read()
int k=0,f=1; char c=getchar();
while(c<\'0\'||c>\'9\')c==\'-\'&&(f=-1),c=getchar();
while(\'0\'<=c&&c<=\'9\')k=k*10+c-\'0\',c=getchar();
return k*f;
inline void pushup(int u)
a[u].sum=a[ls].sum+a[rs].sum;
inline void pushdown(int u)
if(!a[u].del) return; long long d=a[u].del; a[u].del=0;
a[ls].del+=d; a[ls].sum+=d*len(ls);
a[rs].del+=d; a[rs].sum+=d*len(rs);
void build(int u,int l,int r)
a[u].l=l; a[u].r=r; a[u].sum=a[u].del=0;
if(l<r) build(ls,l,mid),build(rs,mid+1,r);
void update(int u,int l,int r,long long d)
if(l<=a[u].l&&a[u].r<=r)
a[u].del+=d; a[u].sum+=d*len(u); return;
pushdown(u);
if(l<=mid) update(ls,l,r,d);
if(r>mid) update(rs,l,r,d);
pushup(u);
long long query(int u,int l,int r)
if(l<=a[u].l&&a[u].r<=r) return a[u].sum;
pushdown(u); long long ret=0;
if(l<=mid) ret+=query(ls,l,r);
if(r>mid) ret+=query(rs,l,r);
return ret;
void dfs1(int x)
size[x]=1; dep[x]=dep[fa[x]]+1;
for(rg int i=0;i<son[x].size();i++)
dfs1(son[x][i]);
size[x]+=size[son[x][i]];
if(size[son[x][i]]>size[heavy[x]]) heavy[x]=son[x][i];
void dfs2(int x,int tp)
top[x]=tp; dfn[x]=++num;
if(heavy[x]) dfs2(heavy[x],tp);
for(rg int i=0;i<son[x].size();i++)
if(son[x][i]!=heavy[x]) dfs2(son[x][i],son[x][i]);
int main()
n=read();
for(rg int i=1;i<n;i++)
int x=read(),y=read();
fa[y]=x; son[x].push_back(y);
if(x==0) rt=x;
dfs1(rt); dfs2(rt,rt);
// for(rg int i=0;i<=n;i++) printf("%d ",size[i]); puts("");
// for(rg int i=0;i<=n;i++) printf("%d ",dfn[i]); puts("");
build(1,1,n);
m=read();
while(m--)
char c=getchar();
while(c!=\'A\'&&c!=\'Q\')c=getchar();
if(c==\'A\')
x=read(),y=read(),z=read();
while(top[x]!=top[y])
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,dfn[top[x]],dfn[x],z);
x=fa[top[x]];
if(dep[x]>dep[y]) swap(x,y);
update(1,dfn[x],dfn[y],z);
else x=read(),printf("%lld\\n",query(1,dfn[x],dfn[x]+size[x]-1));
return 0;
luogu3833shoi2012魔法树(代码片段)
题目描述HarryPotter新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u]<u。初始时，这棵... 查看详情
p3833[shoi2012]魔法树(代码片段)
简单的树链剖分，自己随便弄个样例就能过。给你一个树，支持两个操作：从u点到v点的路径上的点的权值都添加上d。查询以u点为根的子树的权值和。唯一可能错的就是1操作了。u到v的路径，显然需要找出他们的lca。那么就分... 查看详情
[shoi2012]魔法树(代码片段)
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=2836[算法] 树链剖分 时间复杂度:O(NlogN^2)[代码] #include<bits/ 查看详情
bzoj2830&洛谷3830：[shoi2012]随机树——题解(代码片段)
https://www.luogu.org/problemnew/show/P3830#sub <-题面看这里~https://www.lydsy.com/JudgeOnline/problem.php?id=2830感觉智商被压制了的一题……后面放吐槽。参考：https://www.cnblogs.com/GuessYCB/p/846249 查看详情
洛谷3830[shoi2012]随机树概率dp(代码片段)
题目输入格式输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的个数。输出格式输出仅有一行，包含一个实数d，四舍五入精确到小数点后6位。如果q=1，则d表示叶结点平均深度的数学期望值；如果q=2，则d表示... 查看详情
[luogu]魔法树(代码片段)
https://www.luogu.org/problemnew/show/P3833树链剖分+线段树为啥会RE？？不解#include<iostream>#include<cstdio>usingnamespacestd;constintN=1e5+10;#defineLLlonglongintn,T,now=1,tim;inttop[N],tree[N],lst[N], 查看详情
洛谷p4332[shoi2014]三叉神经树题解(代码片段)
一、题目：洛谷原题二、思路：这道题怎么说呢？只能说有点意思，让我第一次见识了LCT怎么应用。首先一个非常明显的性质，就是比如我现在修改了某个叶子结点，记为\\(leaf\\)，那么因此而状态发生改变的点一定是从\\(leaf\\)... 查看详情
[shoi2012]随机树
题面在这里题意随机生成一棵(n)个叶节点的二叉树,方法是从根节点开始,每次等概率选择一个叶子节点(一开始根节点同时也是叶子节点)并生成其左右儿子(称为一次展开),直到该树有(n)个叶节点为止给定(nleq100),求其叶节点平均深... 查看详情
洛谷p3924康娜的线段树
P3924康娜的线段树题目描述小林是个程序媛，不可避免地康娜对这种人类的“魔法”产生了浓厚的兴趣，于是小林开始教她OI。今天康娜学习了一种叫做线段树的神奇魔法，这种魔法可以维护一段区间的信息，是非常厉害的... 查看详情
p3830[shoi2012]随机树(代码片段)
P3830[SHOI2012]随机树链接分析： 第一问：f[i]表示有i个叶子结点的时候的平均深度，$f[i]=\fracf[i-1]+2+f[i-1]*(i-1)2$，表示新增加一个叶子结点，深度增加2，加权后取平均值。 第二问：f[i][j]表示有i个叶子结点，树的深度大于... 查看详情
p3830[shoi2012]随机树题解(代码片段)
...没一个看得懂的，我还是太弱了。题目链接 P3830 [SHOI2012]随机树 题目描述输入输出格式输入格式： 输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的个数。 输出格式： 输出仅有一行，包... 查看详情
luogup3830[shoi2012]随机树期望概率+动态规划+结论(代码片段)
题意非常的复杂，考虑转化一下：每次选择一个叶节点，删除本叶节点（深度为$dep$）的同时，加入两个深度为$dep+1$的叶节点，重复$n$轮首先考虑第$1$问，（你看我这种人相信数据绝对是最大的数据，直接$f[i][S]$表示$i$个叶子结... 查看详情
noip2012第一试模拟题魔法树solution
题意Solution压位+前缀和1#include<cstdio>2#include<iostream>3#include<cmath>4#include<algorithm>5#definellint6usingnamespacestd;7constllmod=100000007;8inlinevoidread(ll&k)9{10llf=1 查看详情
洛谷-p2163[shoi2007]园丁的烦恼(离线二维数点)(代码片段)
题目链接：点击查看题目大意：二维平面坐标系中给出nnn个坐标点，然后是mmm次询问，每次询问需要回答一个闭合矩阵中有多少个点题目分析：想挂树套树来着，但是复杂度有点大。本题不带修且可以离线... 查看详情
洛谷p3252[jloi2012]树
P3252[JLOI2012]树题目描述在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路... 查看详情
洛谷p2119魔法阵
P2119魔法阵题目描述六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。大魔法师有m个魔法物品，编号分别为1,2,...,m。每个物品具有一个魔法值，我们用Xi表示编号为i的物品的魔法值。每个魔法值... 查看详情
洛谷p2119魔法阵
题目描述六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。大魔法师有m个魔法物品，编号分别为1,2,...,m。每个物品具有一个魔法值，我们用Xi表示编号为i的物品的魔法值。每个魔法值Xi是不超过... 查看详情
洛谷p3252[jloi2012]树
题目描述在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路径不必一定从... 查看详情