数据结构3学习笔记

笔记

替罪羊树套主席树

带插入询问区间第k小

题目大意：

给定一个初始长度为 n 的序列，现在有 q 次操作，操作有三种：1.询问区间 [l,r] 内的第 k 小值。2.修改一个位置 i 上的数ai变成 x 。3.在从左往右第 x 个位置后插入一个新的元素，值为 y 。强制在线。
值域在[0,70000]

题解

总结一下
内层是一个主席树，节点都要动态开，满足加入一个数，删除一个主席树（意思是删除这条主席树新创造出来的$O(\log n)$个节点）如果这个主席树的点被别人用了，就不删除它，所以每个点还要维护一下在几棵树里
还要满足合并……debug了那么久就是合并抄错了，建一个新树，这个新的节点的sum是用来合并的两棵树的加和

外层是一个替罪羊树，替罪羊树由于不用旋转可以比较快的维护
要满足暴力重建（拍扁重建233），修改（将沿路的节点减去旧值加上新值一样，主席树的删除和增加），插入（沿路在主席树里加上新值，然后找这条路径上最高的不满足平衡条件的点，暴力重建），询问（找到一些主席树的根节点和一些单个节点值，每层节点个数不超过4个，外层二分答案，所以询问一次$O(\log ^2 n)$）

代码

#include <cstdio>
#include <cmath>
#include <iostream>
//#define ivorysi
using namespace std;
const int V = 70000,N=72000;
const double alphaS = 0.75;
struct node {
    node *lc,*rc;
    int sum,cnt;
}*null,pool[10000005],*tail = pool,*rec[10000005];
int top;
node *getnull() {
    node *res = tail++;
    res->sum = 0;
    res->lc = res->rc = res;
    res->cnt = 1;
    return res;
}
node *Newnode() {
    node *res;
    if(top!=0) res = rec[top--];
    else res = tail++; 
    res->lc = res->rc = null;
    res->cnt = 1;
    return res;
}
void del(node *&p) {
    if(p && !--p->cnt) {
        rec[++top] = p;
        del(p->lc);
        del(p->rc);
        p = NULL;
    }
}
node* add(node *x,const int &l,const int &r,const int &p,const int &delta) {
    if(x->sum + delta == 0) {
        ++null->cnt;
        return null;
    }
    node *res = Newnode();
    res->sum = x->sum + delta;
    res->lc = x->lc; res->rc = x->rc;
    ++res->lc->cnt; ++res->rc->cnt;
    if(l==r) return res;
    int mid = (l + r) >>1;
    if(p<=mid) {
        --res->lc->cnt;
        res->lc = add(x->lc,l,mid,p,delta);
    }
    else {
        --res->rc->cnt;
        res->rc = add(x->rc,mid+1,r,p,delta);
    }
    return res;
}
node *merge(node *x,node *y) {
    if(y==null) {
        ++x->cnt;
        return x;
    }
    if(x==null) {
        ++y->cnt;
        return y;
    }
    node *res=Newnode();
    res->lc = merge(x->lc,y->lc);
    res->rc = merge(x->rc,y->rc);
    res->sum = x->sum + y->sum;
    return res;
}
struct scap_node {
    node *seg;
    scap_node *lc,*rc;
    int size,val;
    void update() {
        node *temp = merge(lc->seg,rc->seg);
        seg = add(temp,0,V,val,1);
        del(temp);
        size = lc->size + rc->size + 1;
    }
}*root,*scap_null,scap_pool[N],*scap_tail=scap_pool;
scap_node* getscap_null() {
    scap_node *res = scap_tail++;
    res->seg = null;
    res->lc = res->rc = res;
    res->size = res->val = 0;
    return res;
}
scap_node* Newscap_node(const int &val) {
    scap_node* res = new scap_node;
    res->val = val;
    res->size = 1;
    res->seg = add(null,0,V,val,1);
    res->lc = res->rc = scap_null;
    return res;
}
scap_node* flatten(scap_node *x,scap_node *y) {
    if(x == scap_null) return y;
    del(x->seg);
    x->rc = flatten(x->rc,y);
    return flatten(x->lc,x);
}
scap_node* build(scap_node *x,const int &n) {
    if(n==0) {
        x->lc = scap_null;
        return x;
    }
    scap_node *y = build(x,n>>1);
    scap_node *z = build(y->rc,n - 1 - (n>>1));
    y->rc = z->lc;
    z->lc = y;
    y->update();
    return z;
}
scap_node* reBuild(scap_node *x) {
    int n = x->size;
    scap_node t;
    t.lc=t.rc=NULL;
    scap_node *head = flatten(x,&t);
    build(head,n);
    return t.lc;
}
int Modify(scap_node *x,const int &p,const int &val) {
    int now = x->lc->size + 1,res;
    if(p < now) res = Modify(x->lc,p,val);
    else if(p > now) res = Modify(x->rc,p-now,val);
    else res = x->val , x->val = val;
    node *temp = x->seg;
    x->seg = add(temp,0,V,res,-1);
    del(temp);
    temp = x->seg;
    x->seg = add(temp,0,V,val,1);
    del(temp);
    return res;
}
scap_node *flag,**fa;
void Insert(scap_node *&x,const int &p,const int &val) {
    if(x == scap_null) {
        x = Newscap_node(val);
        return ;
    }
    ++x->size;
    node *temp = x->seg;
    x->seg = add(temp,0,V,val,1);
    del(temp);
    int now = x->lc->size + 1;
    p<=now ? Insert(x->lc,p,val) : Insert(x->rc,p-now,val);
    int S = alphaS * x->size;
    if(x->lc->size > S || x->rc->size > S) {
        flag=x;
        fa=NULL;
    }
    if(x->lc == flag) fa = &x->lc;
    else if(x->rc == flag) fa = &x->rc;
}
int a[N],lenA,lenB;
node *b[N];
void Query(scap_node *x,int l,int r) {
    if(x == scap_null) return;
    if(l == 1 && r== x->size) {
        b[++lenB] = x->seg;
        return ;
    }
    int mid = x->lc->size + 1;
    if(l <= mid && r >= mid) a[++lenA] = x->val;
    if(r == mid) --r;
    if(l == mid) ++l;
    if(r < l) return ;
    if(r < mid) Query(x->lc,l,r);
    else if(l > mid) Query(x->rc,l-mid,r-mid);
    else {
        Query(x->lc,l,mid-1);
        Query(x->rc,1,r-mid);
    }
}
int Solve(const int &l,const int &r,int k) {
    lenA = 0,lenB = 0;
    Query(root,l,r);
    int L = 0,R = V;
    while(L < R) {
        int mid = (L+R)>>1;
        int sum = 0;
        for (int i = 1 ;i <= lenA ; ++i) {
            if(a[i] >= L && a[i] <= mid) ++sum;
        }
        for (int i = 1 ;i <= lenB ; ++i) {
            sum += b[i]->lc->sum;
        }
        if(sum >= k) {
            for(int i = 1;i <= lenB;++i) {
                b[i] = b[i]->lc;
            }
            R = mid;
        }
        else {
            k-=sum;
            for(int i = 1;i <= lenB;++i) {
                b[i] = b[i]->rc;
            }
            L = mid+1;
        }
    }
    return R;
}
scap_node* Init(int l,int r) {
    if(r < l) return scap_null;
    int mid = (l + r)>>1;
    scap_node *res = Newscap_node(a[mid]); 
    res->lc = Init(l,mid-1);
    res->rc = Init(mid+1,r);
    res->update();
    return res;
} 
int n,Q;
char op[5];
void dfs(scap_node *u) {
    if(u==scap_null) return;
    dfs(u->lc);
    printf("%d ",u->val);
    dfs(u->rc);
} 
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    null = getnull();
    scap_null = getscap_null();
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) {
        scanf("%d",&a[i]);
    }
    root = Init(1,n);
    int lastans=0;
    int x,y,k;
    scanf("%d",&Q);
    while(Q--) {
        scanf("%s",op+1);
        scanf("%d%d",&x,&y);
        if(op[1] == 'Q') {
            scanf("%d",&k);
            x^=lastans;y^=lastans;k^=lastans;
            printf("%d\n",lastans = Solve(x,y,k));
        }
        else if(op[1] == 'M') {
            x^=lastans;y^=lastans;
            Modify(root,x,y);
        }
        else {
            flag = scap_null;
            fa=NULL;
            x^=lastans;y^=lastans;
            Insert(root,x,y);
            if(flag != scap_null) {
                flag = reBuild(flag);
                if(fa != NULL) *fa = flag;
                else root = flag;
            }
        }
    }
}

UOJ #55. 【WC2014】紫荆花之恋

强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。
仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点，每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 i都有一个感受能力值 ri，小精灵 i,j成为朋友当且仅当在树上 i和 j的距离 dist(i,j)≤ri+rjdist(i,j)≤ri+rj，其中 dist(i,j)dist(i,j) 表示在这个树上从 i到 j 的唯一路径上所有边的边权和。
强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。
我们假定这个树一开始为空，节点按照加入的顺序从 1开始编号。由于强强非常好奇，你必须在他每次出现新结点后马上给出总共的朋友对数，不能拖延哦。

输入格式

第一行包含一个整数，表示测试点编号。
第二行包含一个正整数 n，表示总共要加入的节点数。
我们令加入节点前的总共朋友对数是 last_ans，在一开始时它的值为 0。
接下来 n 行中第 i 行有三个非负整数 ai,ci,ri，表示结点 i的父节点的编号为 ai xor(last_ans mod 10^9)（其中 xor 表示异或，mod表示取余，数据保证这样操作后得到的结果介于 1 到 i−1 之间），与父结点之间的边权为 ci，节点 i 上小精灵的感受能力值为 ri。
注意 a1=c1=0，表示 11 号节点是根结点，对于 i>1，父节点的编号至少为 1。

输出格式

包含 n 行，每行输出 1 个整数，表示加入第 i 个点之后，树上有几对朋友。

样例一

input

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

output

0
1
2
4
7

样例二

见样例数据下载。
限制与约定
对于所有数据，满足 1≤ci≤10000，ai≤2×10^9，ri≤10^9。

题解

这道题和替罪羊树的关系并不大，这个东西就是借用了替罪羊树的思想
如果树一开始是给定的，那么我们可以点分治
那么点分治在路上形成的一些树，就是我们对每个节点用作计算的树，由于每次拿的都是重心，所以每个节点所在的树不会超过$\log n$
我们新加入一个节点，就在它所在的每棵树里加上它，如果某棵树失去了平衡，我们对它暴力重新分治

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
//#define ivorysi
#define PII pair<int,int>
#define FI first
#define SE second
typedef long long ll;
typedef unsigned int u32;
using namespace std;
const int N = 1e5 + 5 , mod = 1e9;
const double alphaS = 0.777666;
struct data {
    int to,next,val;
}edge[N*2];
int head[N],sumedge;
int dist[N],size[N],son[N],fa[N];
int n,test_num,R[N];
int que[N],q_n;
bool vis[N];
ll last_ans;
vector<PII> anc[N];
vector<int> sonS[N];
void add(int u,int v,int c) {
    edge[++sumedge].to = v;
    edge[sumedge].val = c;
    edge[sumedge].next = head[u];
    head[u] = sumedge;
}
void addtwo(int u,int v,int c) {
    add(u,v,c);add(v,u,c);
}
namespace Treap {
    u32 Rand() {
        static u32 x = 998666131;
        return x += x << 2 | 1; 
    }
    struct node {
        u32 pri;
        node *lc,*rc;
        int val,size;
        void Reset(const int &v) {
            val = v;
            size = 1;
            lc = rc = NULL;
            pri = Rand();//Treap的魅力在于听天由命
        }
        void update() {
            size = (lc ? lc->size : 0) + 1 + (rc ? rc->size : 0);
        }
    }pool[4000005],*tail = pool,*rec[4000005],*rt_self[N],*rt_fa[N];
    int top = 0;
    node *Newnode(const int &v) {
        node *res;
        if(top!=0) { res = rec[top--];}
        else res = tail++;
        res->Reset(v);
        return res;
    }
    void del(node *&p) {//内存回收机制
        if(!p) return;
        rec[++top] = p;
        del(p->lc);
        del(p->rc);
        p = NULL;
    }
    void Zig(node *&u) {//右旋（左儿子提根）
        node *v = u->lc;
        u->lc = v->rc;
        v->rc = u;
        v->size = u->size;
        u->update();
        u = v;
    }
    void Zag(node *&u) {//左旋（右儿子提根）
        node *v = u->rc;
        u->rc = v->lc;
        v->lc = u;
        v->size = u->size;
        u->update();
        u = v;
    }
    void Insert(node *&u,int val) {
        if(u == NULL) {
            u = Newnode(val);
            return ;
        }
        ++u->size;
        if(val <= u->val) {
            Insert(u->lc,val);
            if(u->lc->pri > u->pri) Zig(u);
        }
        else {
            Insert(u->rc,val);
            if(u->rc->pri > u->pri) Zag(u);
        }
    }
    int Qrank(node *u,int val) {
        if(!u) return 0;
        if(val < u->val) return Qrank(u->lc,val);
        else return (u->lc ? u->lc->size : 0) + 1 + Qrank(u->rc,val);
    }
}
int calc(const int &st) {//计算重心
    que[q_n = 1] = st;
    fa[st] = 0;
    for(int j = 1 ; j <= q_n ; ++j) {
        int u = que[j];
        size[u] = 1;son[u] = 0;
        for(int i = head[u] ; i ; i = edge[i].next) {
            int v = edge[i].to;
            if((!vis[v]) && v != fa[u]) {
                fa[v] = u;
                que[++q_n] = v;
            }
        }
    }
    int grav = -1,maxval = 0x3f3f3f3f;
    for(int i = q_n;i >= 1 ; --i) {
        int u = que[i];
        size[fa[u]] += size[u];
        if(size[u] > son[fa[u]]) son[fa[u]] = size[u];
        if(son[u] < q_n - size[u]) son[u] = q_n - size[u];
        if(maxval > son[u] || grav == -1) {
            grav = u;
            maxval = son[u];
        }
    }
    size[0] = 0;son[0] = 0;
    return grav;
}
void divide_and_conquer(const int &u,const int &fa_u) {
    int grav = calc(u);
    que[q_n = 1] = grav;
    vis[grav] = true;dist[grav] = 0;
    fa[grav] = 0;
    for(int j = 1 ; j <= q_n ; ++j) {
        int u = que[j];
        for(int i = head[u] ; i ; i = edge[i].next) {
            int v = edge[i].to;
            if((!vis[v]) && v != fa[u]) {
                fa[v] = u;
                que[++q_n] = v;
                dist[v] = dist[u] + edge[i].val;
            }
        }
    }
    for(int i = 1 ; i <= q_n ; ++i) {
        int u = que[i];
        anc[u].push_back(make_pair(grav,dist[u]));
        sonS[grav].push_back(u);
        Treap::Insert(Treap::rt_self[grav],dist[u] - R[u]);
        if(fa_u != 0) {
            Treap::Insert(Treap::rt_fa[grav],anc[u][anc[u].size() - 2].SE - R[u]);
        }
    }
    for(int i = head[grav] ; i ; i = edge[i].next) {
        int v = edge[i].to;
        if(!vis[v]) divide_and_conquer(v,grav);
    } 
}
void ReBuild(const int &u,const int &fa_u) {
    vector<int> tmpson = sonS[u];
    int sav = anc[fa_u].size();
    int s = tmpson.size();
    for(int i = 0 ; i < s ; ++i) {
        int v = tmpson[i];
        vis[v] = false;//将这棵树里所有东西都清空
        sonS[v].clear();
        anc[v].resize(sav);//只保留每个点在这棵树被分治之前所在点分树的重心
        Treap::del(Treap::rt_self[v]);
        Treap::del(Treap::rt_fa[v]);
    }
    divide_and_conquer(u,fa_u);
}
void check(const int &u) {
    vis[u] = true;
    int s = anc[u].size();
    for(int i = 0 ; i < s; ++i) {
        Treap::Insert(Treap::rt_self[anc[u][i].FI],anc[u][i].SE - R[u]);
        if(i != 0) {
            Treap::Insert(Treap::rt_fa[anc[u][i].FI],anc[u][i - 1].SE - R[u]);
        }
        //rt_fa存的就是这棵树里面的节点的值和的上一棵树的重心的值
        //用来去重
    }
    for(int i = 0 ; i < s - 1; ++i) {
        int sze_fa = Treap::rt_self[anc[u][i].FI]->size;
        int sze_son = Treap::rt_self[anc[u][i + 1].FI]->size;
        if(sze_fa <= 30) break;
        if(sze_son > alphaS * sze_fa) {//如果这个儿子过大就暴力重建
            ReBuild(anc[u][i].FI,(i ? anc[u][i - 1].FI : 0));
            break;
        }
    }
}
int calc_ans(const int &u,const int &v,const int &w) {
    int res = 0;
    anc[u] = anc[v];
    anc[u].push_back(make_pair(u,-w));
    int s = anc[u].size();
    for(int i = 0 ; i < s ; ++i) {
        anc[u][i].SE += w;
        sonS[anc[u][i].FI].push_back(u);
        res += Treap::Qrank(Treap::rt_self[anc[u][i].FI],R[u] - anc[u][i].SE);
        //加上这棵树中新增加的路径条数
        if(i != 0) {
            res -= Treap::Qrank(Treap::rt_fa[anc[u][i].FI],R[u] - anc[u][i - 1].SE);
            //减去前一棵树不合法的路径条数（起点和终点在同一棵子树）
        }
    }
    return res;
}
int main(int argc, char const *argv[]) {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&test_num);
    scanf("%d",&n);
    last_ans = 0;
    int fa_i,c;
    /*
    树分治中，要求每条路径都经过重心，那么我们可以把距离设成距离重心的距离
    dist[u] + dist[v] <= R[u] + R[v]
    dist[u] - R[u] <= R[v] - dist[v]
    那么新加入一个点，就把这个点的R[v] - dist[v]加入，查找以重心为根的这棵树里
    比它小或等于它的有多少个
    */
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d",&fa_i,&c,&R[i]);
        fa_i ^= (last_ans % mod);
        if(i == 1) {
            anc[i].push_back(make_pair(i,0));
            //anc序列里记录的是：重心 这个点到重心的距离，从一开始分治到最后的树的序列
            sonS[i].push_back(i);
            //sonS[u]是以u为根的点分治树都有哪些节点
            Treap::Insert(Treap::rt_self[i],0 - R[i]);
            //rt_self[u]是u当根的时候dist[u] - R[u]的取值
            puts("0");
            vis[1] = 1;
            //忘记给1打上标记了……GG，这样会让某个1的儿子多更新很多东西，从而让vector申请的空间超限
            continue;
        }
        addtwo(fa_i,i,c);
        last_ans += calc_ans(i,fa_i,c);
        check(i);
        printf("%lld\n",last_ans);
    }
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 100005
struct node {
    int to,next;
}edge[MAXN*2];
int head[MAXN],sumedge;
void add(int u,int v) {
    edge[++sumedge].to = v;
    edge[sumedge].next = head[u];
    head[u] = sumedge;
}
void addtwo(int u,int v) {
    add(u,v);add(v,u);
}
struct data {
    int lc,rc;
    ll sum,tagA,tagB;
}tr[MAXN*20];
int nodecnt;
int n,m,top[MAXN],seq,son[MAXN],fa[MAXN],size[MAXN],que[MAXN],q_n,pos[MAXN];
int cur_time,last[MAXN],times,rt[MAXN],tot;
ll lastans = 0;
void Bfs() {
    que[q_n = 1] = 1;
    for(int i = 1 ; i <= q_n ; ++i) {
    int u = que[i];
    size[u] = 1;son[u] = 0;
    for(int j = head[u] ; j ; j = edge[j].next) {
        int v = edge[j].to;
        if(v != fa[u]) {
        fa[v] = u;
        que[++q_n] = v;
        }
    }
    }
    for(int i = q_n ; i >= 2 ; --i) {
    int u = que[i];
    size[fa[u]] += size[u];
    if(size[u] > size[son[fa[u]]]) son[fa[u]] = u;
    }
    for(int i = 1 ; i <= q_n ; ++i) {
    int u = que[i];
    if(!top[u]) {
        for(int y = u ; y ; y = son[y]) {
        top[y] = u;
        pos[y] = ++seq;
        } 
    }
    }
}
int getlen(int x,int y) {
    int res = 0;
    while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) swap(x,y);
    res += dep[x] - dep[top[x]] + 1;
    x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x,y);
    res += dep[x] - dep[y] + 1;
    return res;
}
ll calc(ll a,ll d,int n) {
    return a * n + n * (n - 1) / 2 * d;
}
void Modify(int &k,int &k1,int l,int r,int x,int y,const ll &A,const ll &B) {
    k = ++nodecnt;
    tr[k].tagA = tr[k1].tagA;
    tr[k].tagB = tr[k1].tagB;
    if(l == x && r == y) {
    tr[k].tagA += A;
    tr[k].tagB += B;
    tr[k].sum = tr[k1].sum + calc(A,B,r - l + 1);
    tr[k].lc = tr[k1].lc;tr[k].rc = tr[k1].rc;
    return ;
    }
    int mid = (l + r) >> 1;
    if(y <= mid) {
    tr[k].rc = tr[k1].rc;
    Modify(tr[k].lc,tr[k1].lc,l,mid,x,y,A,B);
    }
    else if(x > mid) {
    tr[k].lc = tr[k1].lc;
    Modify(tr[k].rc,tr[k1].rc,mid+1,r,x,y,A,B);
    }
    else {
    Modify(tr[k].lc,tr[k1].lc,l,mid,x,mid,A,B);
    Modify(tr[k].rc,tr[k1].rc,mid+1,r,mid+1,y,A + (mid - x + 1) * B,B);
    }
    tr[k].sum = tr[tr[k].lc].sum + tr[tr[k].rc].sum;
}
void PathModify(int x,int y,ll A,ll B) {
    int len = getlen(x,y);
    while(top[x] != top[y]) {
    if(dep[top[x]] > dep[top[y]]) {
        Modify(rt[++tot],rt[cur_time],1,n,
           pos[top[x]],pos[x],A + B * (dep[x] - dep[top[x]]),-B);
        len -= dep[x] - dep[top[x]] + 1;
        A += B * (dep[x] - dep[top[x]] + 1);
        x = fa[top[x]];
        cur_time = tot;
    }
    else {
        Modify(rt[++tot],rt[cur_time],1,n,pos[top[y]],pos[y],
           A + B * (len - (dep[y] - dep[top[y]] + 1)),B);
        len -= dep[y] - dep[top[y]] + 1;
        y = fa[top[y]];
        cur_time = tot;
    }
    }
    if(dep[x] > dep[y]) {
    Modify(rt[++tot],rt[cur_time],1,n,pos[y],pos[x],A + B * (dep[x] - dep[y]),-B);
    }
    else {
    Modify(rt[++tot],rt[cur_time],1,n,pos[x],pos[y],A,B);
    }
    cur_time = tot;
}
ll Query(int k,int l,int r,int x,int y,const ll &A,const ll &B) {
    if(l == x && r == y) {
    return tr[k].sum + calc(A,B,r - l + 1);
    }
    int mid = (l + r) >> 1;
    if(y <= mid) {
    return Query(tr[k].lc,l,mid,x,y,A + tr[k].tagA + tr[k].tagB * (x - l),B + tr[k].tagB);
    }
    else if(x > mid) {
    return Query(tr[k].rc,mid + 1,r,x,y,
             A + tr[k].tagA + tr[k].tagB * (x - l),B + tr[k].tagB);
    }
    else {
    return Query(tr[k].lc,l,mid,x,mid,
             A + tr[k].tagA + tr[k].tagB * (x - l),B + tr[k].tagB) +
        Query(tr[k].rc,mid + 1,r,mid + 1,y,
          A + tr[k].tagA * (mid - l + 1),B + tr[k].tagB);
    }
}
ll PathQuery(int x,int y) {
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&n);
    int u,v;
    for(int i = 1 ; i < n ; ++i) {
    scanf("%d%d",&u,&v);
    addtwo(u,v);
    }
    Bfs();
    while(m--) {
    }
    return 0;
}

Observing the Tree Problem Code: QUERY

All submissions for this problem are available.
Chef gives you a tree, consisting of N nodes. The nodes are numbered from 1 to N, and each node has an integer, which is equal to 0 initially. Then, Chef asks you to perform M queries.
The first type of queries is changing: here, you are given integers X, Y, A and B. Add A to the integer, associated with the node X, then add A+B to the integer, associated with the second node on the way from X to Y, then add A+2*B to the integer, associated with the third node on the way from X to Y, and so on. As you know, there is only one simple path from X to Y.
The second type of queries is a question: here, you are given integers X and Y. Output the sum of all integers, associated with nodes on the way from X to Y.
The third type of queries is a rollback: here, you are given an integer X. All the integers associated with the nodes return to the state after the X-th changing query. If X is 0, then all of them become equal to zero, as in the very beginning.

Input

The first line of an input consists of two integers - N and M.
Then, N−1 lines follow. These N−1 lines describe the tree structure. Each line consists of two integers - X and Y, and that means that there is an edge between node X and node Y.
Then, M lines follow. A single line denotes a single query, which has one of the following forms: (See the sample for the detailed explanation)
c X1 Y1 A B - changing query,
q X1 Y1 - question query,
l X1 - rollback query.
As you can see, the numbers X and Y aren't given to you directly. For the rollback query, actual number X will be equal to (X1+lastans) modulo (total number of changing queries before this query + 1). For the changing and question queries, X will be equal to ((X1+lastans) modulo N)+1 and Y will be equal to ((Y1+lastans) modulo N)+1, where lastans denotes the last number that you have output, or zero if you haven't output any numbers yet.

Output

For each question query output the answer on a single line.

Constraints

1 ≤ N, M ≤ 100000 (105)
0 ≤ A, B ≤ 1000
0 ≤ X1, Y1 ≤ 100000 (105)

Example

Input:

5 7
1 2
2 3
3 4
4 5
c 1 4 2 3
c 2 3 5 10
q 1 3
l 1
q 1 3
l 1
q 1 3

Output:

35
0
15

Explanation

As you can see, the tree in the sample is like a line. Let's denote the first state of integers 0 0 0 0 0, where the i-th integer means the integer associated with the node i.
In the first changing query "c 1 4 2 3", the actual numbers are X = (1 + 0) modulo 5 + 1 = 2, Y = (4 + 0) modulo 5 + 1 = 5. Hence the state will be 0 2 5 8 11 after this query.
After the second changing query "c 2 3 5 10", the state will be 0 2 10 23 11 for similar reason.
In the next question query, the actual numbers are X = (1 + 0) modulo 5 + 1 = 2, Y = (3 + 0) modulo 5 + 1 = 4. Hence the answer must be 2 + 10 + 23 = 35.
In the first rollback query "l 1", the actual number is X = (1 + 35) modulo (2 + 1) = 36 modulo 3 = 0, since lastans = 36. Thus the state will be rollbacked to 0 0 0 0 0.
Then the answer of the next question query "q 1 3" must be 0, because all integers are currently 0.
In the second rollback query "l 1", the actual number is X = (1 + 0) modulo (2 + 1) = 1, since lastans = 0. Thus the state will be 0 2 5 8 11, which is the state after the first changing query.
Then the answer of the last question query must be 2 + 5 + 8 = 15.

题解

给出一棵树，要求维护一下三种操作
c x y a b 表示在x到y的路径上增加一个等差数列，首项为a公差为b
q x y表示x到y路径上的点权和
l x表示回到某一次修改后版本
强制在线

那么这就要用到可持久化了……我们树链剖分得用dfs序来，建一棵大树
每次累加的时候打上标记，经过的区间全都加上等差数列的总和，询问的时候要累加上根节点到询问节点所有标记，修改就是新建节点
好像……就没什么了？？？
然而这道题教会我的更多……我都学会了如何写随机生成一棵树的代码了
这个bug令我头秃

return Query(tr[k].lc,l,mid,x,mid,
                 A + tr[k].tagA + tr[k].tagB * (x - l),B + tr[k].tagB) +
            Query(tr[k].rc,mid + 1,r,mid + 1,y,
              A + tr[k].tagA + tr[k].tagB * (mid - l + 1),B + tr[k].tagB);

似乎没什么不对的？？？

return Query(tr[k].lc,l,mid,x,mid,
                 A + tr[k].tagA + tr[k].tagB * (x - l),B + tr[k].tagB) +
            Query(tr[k].rc,mid + 1,r,mid + 1,y,
              A + B * (mid + 1 - l) + tr[k].tagA + tr[k].tagB * (mid - l + 1),B + tr[k].tagB);

实际上原来的A都变成新的啦！！！
因为AB都是维护[x,y]区间的，线段树上区间断两半的时候，A也要更新啊……
本来，我是发现不了这个bug的，然而我觉得这样写有点啰嗦，然后改成了别的写法……结果就……跑过了我的随机数据……结果就A了！！！
然后我才知道query函数错了，苦思冥想才发现原来是这样
代码还是贴清晰易懂一点的吧，函数太长导致分行也太蠢了2333

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
//#define ivorysi
#define MAXN 200005
using namespace std;
typedef long long ll;
struct node {
    int to,next;
}edge[MAXN*2];
int head[MAXN],sumedge;
void add(int u,int v) {
    edge[++sumedge].to = v;
    edge[sumedge].next = head[u];
    head[u] = sumedge;
}
void addtwo(int u,int v) {
    add(u,v);add(v,u);
}
struct data {
    int lc,rc;
    ll sum,tagA,tagB;
}tr[MAXN*300];
int nodecnt;
int n,m,top[MAXN],seq,son[MAXN],fa[MAXN],size[MAXN],que[MAXN],q_n,pos[MAXN],dep[MAXN];
int cur_time,last[MAXN],times,rt[3000005],tot;
ll lastans = 0;
char s;
void Bfs() {
    que[q_n = 1] = 1;
    dep[1] = 1;
    for(int i = 1 ; i <= q_n ; ++i) {
        int u = que[i];
        size[u] = 1;son[u] = 0;
        for(int j = head[u] ; j ; j = edge[j].next) {
            int v = edge[j].to;
            if(v != fa[u]) {
                dep[v] = dep[u] + 1;
                fa[v] = u;
                que[++q_n] = v;
            }
        }
    }
    for(int i = q_n ; i >= 2 ; --i) {
        int u = que[i];
        size[fa[u]] += size[u];
        if(size[u] > size[son[fa[u]]]) son[fa[u]] = u;
    }
    for(int i = 1 ; i <= q_n ; ++i) {
        int u = que[i];
        if(!top[u]) {
            for(int y = u ; y ; y = son[y]) {
                top[y] = u;
                pos[y] = ++seq;
            } 
        }
    }
}
int getlen(int x,int y) {
    int res = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        res += dep[x] - dep[top[x]] + 1;
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x,y);
    res += dep[x] - dep[y] + 1;
    return res;
}
ll calc(ll a,ll d,int n) {
    return a * n + 1LL * n * (n - 1) / 2 * d;
}
void Modify(int &k,const int &k1,const int &l,const int &r,const int &x,const int &y,const ll &A,const ll &B) {
    k = ++nodecnt;
    tr[k].tagA = tr[k1].tagA;
    tr[k].tagB = tr[k1].tagB;
    tr[k].sum = tr[k1].sum + calc(A,B,y - x + 1);
    if(l == x && r == y) {
        tr[k].tagA += A;
        tr[k].tagB += B;
        tr[k].lc = tr[k1].lc;tr[k].rc = tr[k1].rc;
        return ;
    }
    int mid = (l + r) >> 1;
    if(y <= mid) {
        tr[k].rc = tr[k1].rc;
        Modify(tr[k].lc,tr[k1].lc,l,mid,x,y,A,B);
    }
    else if(x > mid) {
        tr[k].lc = tr[k1].lc;
        Modify(tr[k].rc,tr[k1].rc,mid+1,r,x,y,A,B);
    }
    else {
        Modify(tr[k].lc,tr[k1].lc,l,mid,x,mid,A,B);
        Modify(tr[k].rc,tr[k1].rc,mid+1,r,mid+1,y,A + (mid - x + 1) * B,B);
    }
}
void PathModify(int x,int y,ll A,ll B) {
    int len = getlen(x,y);
    while(top[x] != top[y]) {
        if(dep[top[x]] > dep[top[y]]) {
            Modify(rt[++tot],rt[cur_time],1,n,
               pos[top[x]],pos[x],A + B * (dep[x] - dep[top[x]]),-B);
            len -= dep[x] - dep[top[x]] + 1;
            A += B * (dep[x] - dep[top[x]] + 1);
            x = fa[top[x]];
            cur_time = tot;
        }
        else {
            Modify(rt[++tot],rt[cur_time],1,n,pos[top[y]],pos[y],
               A + B * (len - (dep[y] - dep[top[y]] + 1)),B);
            len -= dep[y] - dep[top[y]] + 1;
            y = fa[top[y]];
            cur_time = tot;
        }
    }
    if(dep[x] > dep[y]) {
        Modify(rt[++tot],rt[cur_time],1,n,pos[y],pos[x],A + B * (dep[x] - dep[y]),-B);
    }
    else {
        Modify(rt[++tot],rt[cur_time],1,n,pos[x],pos[y],A,B);
    }
    cur_time = tot;
}
ll Query(const int &k,const int &l,const int &r,const int &x,const int &y) {
    if(l == x && r == y) {
        return tr[k].sum;
    }
    int mid = (l + r) >> 1;
    ll res;
    if(y <= mid) {
        res = Query(tr[k].lc,l,mid,x,y);
    }
    else if(x > mid) {
        res = Query(tr[k].rc,mid + 1,r,x,y);
    }
    else {
        res = Query(tr[k].lc,l,mid,x,mid) + Query(tr[k].rc,mid + 1,r,mid + 1,y);
    }
    res += calc(tr[k].tagA + tr[k].tagB * (x - l),tr[k].tagB,y - x + 1);
    return res;
}
ll PathQuery(int x,int y) {
    ll res = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        res += Query(rt[cur_time],1,n,pos[top[x]],pos[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    res += Query(rt[cur_time],1,n,pos[x],pos[y]);
    return res;
}
void change(int &x) {
    x = (lastans + x) % n + 1;
}
int read() {
    char c = getchar();
    int res = 0;
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res;
}
void out(ll x) {
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    n = read();m = read();
    for(int i = 1 ; i < n ; ++i) {
        addtwo(read(),read());
    }
    Bfs();
    int x,y,a,b;
    int cnt = 0;
    while(m--) {
        s = getchar();
        while(s < 'a' || s > 'z') s = getchar();
        if(s == 'c') {
            x = read();y = read();a = read();b = read();
            change(x);change(y);
            PathModify(x,y,a,b);
            last[++times] = cur_time;
        }
        else if(s == 'q') {
            ++cnt;
            x = read();y = read();
            change(x);change(y);
            lastans = PathQuery(x,y);
            out(lastans);
            putchar('\n');
        }
        else if(s == 'l'){
            x = read();
            x = 1LL * (x + lastans) % (times + 1);
            cur_time = last[x];
        }
    }
    return 0;
}