正文 

当前位置： 首页 > IT > java教程

luogu3833shoi2012魔法树(代码片段)

rlddd rlddd     2022-12-27     771

关键词：

题目描述

Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。

这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u] < u。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即0个果子）。

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：

Add u v d

表示将点u和v之间的路径上的所有节点的果子个数都加上d。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：

Query u

表示当前果树中，以点u为根的子树中，总共有多少个果子？


输入

第一行一个正整数N (1 ≤ N ≤ 100000)，表示果树的节点总数，节点以0,1,…,N ? 1标号，0一定代表根节点。

接下来N ? 1行，每行两个整数a,b (0 ≤ a < b < N)，表示a是b的父亲。

接下来是一个正整数Q(1 ≤ ? ≤ 100000)，表示共有Q次操作。

后面跟着Q行，每行是以下两种中的一种：

  1. A u v d，表示将u到v的路径上的所有节点的果子数加上d；0 ≤ u,v <N,0 < d < 100000

  2. Q u，表示询问以u为根的子树中的总果子数，注意是包括u本身的。


输出

对于所有的Query操作，依次输出询问的答案，每行一个。答案可能会超过2^32 ，但不会超过10^15 。


样例输入

4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2


样例输出

3
3
2

 


题解

树剖模版。

 

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=1e5+5;
const int maxm=2e5+5;

ll fir[maxn],to[maxm],nex[maxm],ecnt;
ll n,m,r,p,w[maxn],cnt,op,x,y,z;
ll wt[maxn],son[maxn],top[maxn],fa[maxn],sz[maxn],dep[maxn],id[maxn];

struct SegmentTree
    ll l,r,v,add;
st[maxn*4];

void add_edge(int u,int v)
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;


void dfs1(int x,int f,int deep)
    dep[x]=deep;
    fa[x]=f;
    sz[x]=1;
    int maxson=-1;
    for(int e=fir[x];e;e=nex[e])
        int v=to[e];
        if(v==f) continue;
        dfs1(v,x,deep+1);
        sz[x]+=sz[v];
        if(sz[v]>maxson) maxson=sz[v],son[x]=v;
    


void dfs2(int x,int topf)
    top[x]=topf;
    id[x]=++cnt;
    wt[cnt]=w[x];
    if(!son[x]) return ;
    dfs2(son[x],topf);
    for(int e=fir[x];e;e=nex[e])
        int v=to[e];
        if(v==fa[x]||v==son[x]) continue;
        dfs2(v,v);
    


void pushup(int root)
    st[root].v=(st[root*2].v+st[root*2+1].v);


void build(int root,int l,int r)
    st[root].l=l;st[root].r=r;
    if(l==r) st[root].v=wt[l];
    else
        int m=l+r>>1;
        build(root*2,l,m);
        build(root*2+1,m+1,r);
        pushup(root);
    


void pushdown(int root)
    st[root*2].v=(st[root*2].v+st[root].add*(st[root*2].r-st[root*2].l+1));
    st[root*2+1].v=(st[root*2+1].v+st[root].add*(st[root*2+1].r-st[root*2+1].l+1));
    st[root*2].add=(st[root*2].add+st[root].add);
    st[root*2+1].add=(st[root*2+1].add+st[root].add);
    st[root].add=0;


void add(int root,int l,int r,int val)
    if(st[root].l>r||st[root].r<l) return ;
    if(st[root].l>=l&&st[root].r<=r)
        st[root].v=(st[root].v+val*(st[root].r-st[root].l+1));
        st[root].add=(st[root].add+val);
    
    else
        pushdown(root);
        add(root*2,l,r,val);
        add(root*2+1,l,r,val);
        pushup(root);
    


ll query(int root,int l,int r)
    if(st[root].l>r||st[root].r<l) return 0;
    if(st[root].l>=l&&st[root].r<=r) return st[root].v;
    pushdown(root);
    return (query(root*2,l,r)+query(root*2+1,l,r));


void Change(int x,int y,int val)
    int f1=top[x],f2=top[y];
    while(f1!=f2)
        if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
        add(1,id[f1],id[x],val);
        x=fa[f1];f1=top[x];
    
    if(dep[x]>dep[y]) swap(x,y);
    add(1,id[x],id[y],val);


ll Query(int x,int y)
    ll f1=top[x],f2=top[y],ans=0;
    while(f1!=f2)
        if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
        ans=(ans+query(1,id[f1],id[x]));
        x=fa[f1];f1=top[x];
    
    if(dep[x]>dep[y]) swap(x,y);
    ans=(ans+query(1,id[x],id[y]));
    return ans;


void Change_tree(int x,int val)
    add(1,id[x],id[x]+sz[x]-1,val);


ll Query_tree(int x)
    return query(1,id[x],id[x]+sz[x]-1);


template<typename T>void read(T& aa)
    char cc; ll ff;aa=0;cc=getchar();ff=1;
    while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar();
    if(cc==‘-‘) ff=-1,cc=getchar();
    while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
    aa*=ff;


int main()
    read(n);
    for(int i=1;i<n;i++)
        read(x),read(y);
        add_edge(x+1,y+1);
        add_edge(y+1,x+1);
    
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,cnt);
    read(m);
    while(m--)
        char o;
        cin>>o;
        if(o==‘A‘)
            read(x),read(y),read(z);
            Change(x+1,y+1,z);
        
        else
            read(x);
            cout<<Query_tree(x+1)<<endl;
        
    
    return 0;

 






p3833[shoi2012]魔法树(代码片段)

简单的树链剖分，自己随便弄个样例就能过。给你一个树，支持两个操作：从u点到v点的路径上的点的权值都添加上d。查询以u点为根的子树的权值和。唯一可能错的就是1操作了。u到v的路径，显然需要找出他们的lca。那么就分... 查看详情

洛谷3833shoi2012魔法树

【题解】　　树链剖分模板题。。#include<cstdio>#include<algorithm>#include<queue>#defineN500010#definergregister#definels(u<<1)#definers(u<<1|1)#definemid((a[u].l+a[u].r)>>1)#defin 查看详情

[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], 查看详情

[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 查看详情

luogu-3829[shoi2012]信用卡凸包(代码片段)

这道题的转化很巧妙，可以把信用卡四个角的圆心看做平面上的点来做凸包，(ans)就是凸包周长加上一个圆的周长//luogu-judger-enable-o2#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintmaxn 查看详情

[luogu3244shoi2016]黑暗前的幻想乡(容斥原理+矩阵树定理)(代码片段)

传送门Description给出n个点和n?1种颜色，每种颜色有若干条边。求这张图多少棵每种颜色的边都出现过的生成树，答案对109+7取模。Input第一行包含一个正整数N(N<=17)，表示城市个数。接下来N-1行，其中第i行表示第i个建筑公司可... 查看详情

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随机树坑题，别人的题解我看了一个下午没一个看得懂的，我还是太弱了。题目链接 P3830 [SHOI2012]随机树 题目描述输入输出格式输入格式： 输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的... 查看详情

洛谷3830[shoi2012]随机树概率dp(代码片段)

题目输入格式输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的个数。输出格式输出仅有一行，包含一个实数d，四舍五入精确到小数点后6位。如果q=1，则d表示叶结点平均深度的数学期望值；如果q=2，则d表示... 查看详情

luogup3830[shoi2012]随机树期望概率+动态规划+结论(代码片段)

题意非常的复杂，考虑转化一下：每次选择一个叶节点，删除本叶节点（深度为$dep$）的同时，加入两个深度为$dep+1$的叶节点，重复$n$轮首先考虑第$1$问，（你看我这种人相信数据绝对是最大的数据，直接$f[i][S]$表示$i$个叶子结... 查看详情

[luogup2161[[shoi2009]会场预约(splay)(代码片段)

 题面传送门:https://www.luogu.org/problemnew/show/P2161    Solutionsplay的确有线段树/树状数组的做法,但我做的时候脑残没想到我们可以考虑写一个类似NOIP2017D2T3列队那道题那样的带分裂的平衡树考虑用splay维护每一条线... 查看详情

[shoi2012]随机树(代码片段)

感觉第一问就非常神仙，还有第二问怎么被我当成组合数学题来做了首先是第一问期望具有线性性，于是深度平均值的期望等于深度和的期望值的平均设(dp_x)表示具有(x)个叶子节点的树的深度和的期望值是多少我们发现扩展一个... 查看详情

排序+模拟魔法照片luogu-1583(代码片段)

题目描述一共有n（n≤20000）个人（以1--n编号）向佳佳要照片，而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序，每人就有了一个序号D[i]... 查看详情

luogup3830[shoi2012]随机树期望dp(代码片段)

LINK：随机树非常经典的期望dp.考虑第一问：设f[i]表示前i个叶子节点的期望平均深度。因为期望具有线性性所以可以由每个叶子节点的期望平均深度得到总体的。(f[i]=(f[i-1]cdot(i-1)+(f[i-1]+1)cdot2-f[i-1])/i=f[i-1]+2/i)考虑第二问：可以设... 查看详情

[shoi2012]随机树

题面在这里题意随机生成一棵(n)个叶节点的二叉树,方法是从根节点开始,每次等概率选择一个叶子节点(一开始根节点同时也是叶子节点)并生成其左右儿子(称为一次展开),直到该树有(n)个叶节点为止给定(nleq100),求其叶节点平均深... 查看详情

p4340[shoi2016]随机序列(线段树)(代码片段)

P4340[SHOI2016]随机序列(线段树)结论：只有前缀积有贡献。因为第一个数前面是没有符号的，除了前缀积外，都可以通过加号变成减号、减号变加号使其贡献抵消。接下来考虑每个前缀积的贡献。我们可以枚举前缀积的... 查看详情

[luogu]树(代码片段)

https://www.luogu.org/problemnew/show/P4092树剖+线段树区间修改，单点查询#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inlineintread()intret;scanf("%d",&ret);returnret;intn,T;intnow=1,head[N] 查看详情