权值线段树，动态开点与线段树合并

Cl41Mi5deeD · 2024-01-16 21:51:54 · 算法·理论

不好吃的线段树半家桶。

权值线段树

本质是叶子节点下标意义的变化。

一般情况下，线段树的每条线段负责维护区间 a_l\sim a_r 的信息。存在两个叶子节点 tree_l,tree_r，有 tree_l.l=tree_l.r=l,tree_r.l=tree_r.r=r。权值线段树表示为：tree_l.l=tree_l.r=a_l,tree_r.l=tree_r.r=a_r。

翻译成人话：用线段树维护桶。

进而可以实现以下操作：

之类的东西。

struct Segment_Tree{
    #define leftson(p) p<<1
    #define rightson(p) p<<1|1
    #define push_up(p) tree[p].val=tree[leftson(p)].val+tree[rightson(p)].val
    struct TREE{
        int l,r;
        int val;//l，r：当前节点所管辖的元素l~r。val：区间内的元素总数
    }tree[MAXN<<2];
    void build(int l,int r,int p){
        tree[p].l=l,tree[p].r=r,tree[p].val=0;
        if(l==r){return;}
        int mid=l+r>>1;
        build(l,mid,leftson(p));
        build(mid+1,r,rightson(p));
        push_up(p);
    }
    void update(int x,int v,int p){//将元素x增加v个
        if(tree[p].l==tree[p].r){
            tree[p].val+=v;
            return;
        }
        int mid=tree[p].l+tree[p].r>>1;
        if(x<=mid)update(x,v,leftson(p));
        else update(x,v,rightson(p));
    }//就是单点修改
    int query(int l,int r,int p){//查询元素l~r内的总元素个数
        if(tree[p].l>=l&&tree[p].r<=r)return tree[p].val;
        int mid=tree[p].l+tree[p].r>>1;
        int res=0;
        if(l<=mid)res+=query(l,r,leftson(p));
        if(r>mid)res+=query(l,r,rightson(p));
        return res;
    }//就是区间查询
    int kth(int k,int p){//查询序列中第k大的元素是哪个
        if(tree[p].l==tree[p].r)return tree[p].l;//找到了返回元素
        int mid=tree[p].l+tree[p].r>>1;
        int s1=tree[leftson(p)].val,s2=tree[rightson(p)].val;//我们令线段树管辖的序列是递增的，右儿子的元素普遍较大
        if(k<=s2)return kth(k,rightson(p));//如果k就在右儿子里就返回
        else return kth(k-s2,leftson(p));//如果k在左儿子里，就找左儿子中第k-s2大的元素。
    }
}ST;

动态开点线段树

我称其为和面流线段树，水多加面面多加水。

一般线段树要开 4N 的空间，事实上需要的点在 1\sim 2N是稠密的，在2N\sim4N 是稀疏的。并且我们根据进制思想，一棵维护区间 a_1\sim a_n 的线段树实际需要的空间为：\sum_{i=0}^{logn}2^i<2n，因此每棵线段树都浪费了至少 2N 的空间。

观察语句：

#define leftson(p) p<<1

#define rightson(p) p<<1|1

这样可以使每个节点 p 的左右儿子编号都是 2p,2p+1 且不出现重复。同时也导致开了大量闲置的叶子节点。

节点编号是可以做到连续的，我们只需指定每个节点的左右儿子编号即可。

至于“水多加面”：只有我们要更新或查询一个先前还没有指定儿子节点变好的节点时，我们才去更新这个点的子节点信息，而不是在 ST.build() 函数中全部写好。

2024.2.5 updated:

可见动态开点线段树是现场钦定儿子的管辖范围的。由于修改一般是单点修改，所以添加一个点一定只会落在一个子节点中，所以在开点时会导致一个节点缺少一个儿子，因为目前那个儿子所管辖的区间还没有元素被加入。

对空间的节省使得动态开点权值线段树拥有天然的离散性，进而如果使用了此数据结构是不需要对值域离散化的。

以下是实现。

struct Segment_Tree{//线段树维护区间修改和单点查询。
    int tot=1,root=1;//tot代表节点编号，root指向树根，因为形如(&p)的函数是无法向其中填入常量(例如1)的。 
    struct TREE{
        int lson,rson;//一个节点所管理的区间和自己的编号没有关系，只和父节点管理的区间有关。
        //如此追溯直到 tree[1].l=1,tree[1].r=n。进而每个节点是不必要也不能定义l,r的。
        int val,tag;
    }tree[MAXN<<1];//只需要二倍空间。然而线段树合并时得开20倍，原因之后说。
    inline void push_up(int p){
        tree[p].val=tree[tree[p].lson].val+tree[tree[p].rson].val;
        return;//此时左右子节点就不是p*2之类的了，是自己定义出来的儿子下标。
    }
    inline void spread(int p,int l,int r){//与一般线段树最大的不同在下放操作。
    //p为父节点的下标，l，r为父节点管辖的区间，由tree[1]递推得来。
        if(!tree[p].lson)tree[p].lson=++tot;
        if(!tree[p].rson)tree[p].rson=++tot;//如果子节点还没用就不管，用了发现没定义就就地定义。
        int mid=l+r>>1;
        tree[tree[p].lson].val+=tree[p].tag*(mid-l+1);//就地赋予子节点管辖区间并作修改。
        tree[tree[p].rson].val+=tree[p].tag*(r-mid);//lson管l~mid,rson为mid+1~r。
        tree[tree[p].lson].tag+=tree[p].tag;
        tree[tree[p].rson].tag+=tree[p].tag;
        tree[p].tag=0;
    }
    inline void update(int l,int r,int k,int ul,int ur,int &p){//由于节点管辖区间不是固定的，所以每次要从[1,n]推得。
    //l,r为当前节点管辖区间，ul,ur为修改区间。
    //当前节点p可能是没开过的，如果真没开过那就就地给父亲节点的儿子赋值就行，所以是&p。
        if(!p)p=++tot;
        if(l>=ul&&r<=ur){
            tree[p].val+=k*(r-l+1);
            tree[p].tag+=k;//和一般线段树一样。
            return;
        }
        spread(p,l,r);//每次下放的父亲节点要指明其管辖区间。
        int mid=l+r>>1;
        if(ul<=mid)update(l,mid,k,ul,ur,tree[p].lson);//安排左子节点区间并修改。
        if(ur>mid)update(mid+1,r,k,ul,ur,tree[p].rson);//安排右子节点区间并修改。
        push_up(p);
    }
    inline int query(int l,int r,int ux,int p){
        if(!p)return 0;//没开过这个点，也就是从来没更新过，直接返回0。
        if(l>=ux&&r<=ux)return tree[p].val;
        spread(p,l,r);
        int mid=l+r>>1;
        int ans=0;
        if(ux<=mid)return query(l,mid,ux,tree[p].lson);
        else return query(mid+1,r,ux,tree[p].rson);//同上操作。
    }
}ST;

例题

将询问按照右端点排序。

这个人在区间上只会采出现了至少两次的花。换句话说，点 a_i 与其颜色 col_i 对答案有贡献，当且仅当 col_i 上次出现的位置 last_{col_i} 满足 l<=last_{col_i}<a_i<=r。预处理一下即可。

令 loc_i 表示 col_i 上次出现的位置，last_i 为 col_i 本次出现的位置，则区间 last_i\sim col_i 上的答案增加 1 贡献，没有 last 就更新一下，有 last 就直接增加答案，用线段树维护区间。

然后就被卡了。

题解里用的是树状数组，也就是说我们以很细小的冗余时间T了本题，那么就可以用动态开点优化，因为没开过的点根本就不用看。

#include<bits/stdc++.h>
#define MAXN 2000005
using namespace std;
int n,c,m;
int col[MAXN],loc[MAXN],last[MAXN];
struct node{
    int l,r,id;
}q[MAXN];
int ans[MAXN];
bool cmp(node a,node b){
    return a.r<b.r;
}
struct Segment_Tree{//上面的板子就是从这粘来的，不解释了。
    int tot=1,root=1;
    struct TREE{
        int lson,rson;
        int val,tag;
    }tree[MAXN<<1];
    inline void push_up(int p){
        tree[p].val=tree[tree[p].lson].val+tree[tree[p].rson].val;
        return;
    }
    inline void spread(int p,int l,int r){
        if(!tree[p].lson)tree[p].lson=++tot;
        if(!tree[p].rson)tree[p].rson=++tot;
        int mid=l+r>>1;
        tree[tree[p].lson].val+=tree[p].tag*(mid-l+1);
        tree[tree[p].rson].val+=tree[p].tag*(r-mid);
        tree[tree[p].lson].tag+=tree[p].tag;
        tree[tree[p].rson].tag+=tree[p].tag;
        tree[p].tag=0;
    }
    inline void update(int l,int r,int k,int ul,int ur,int &p){
        if(!p)p=++tot;
        if(l>=ul&&r<=ur){
            tree[p].val+=k*(r-l+1);
            tree[p].tag+=k;
            return;
        }
        spread(p,l,r);
        int mid=l+r>>1;
        if(ul<=mid)update(l,mid,k,ul,ur,tree[p].lson);
        if(ur>mid)update(mid+1,r,k,ul,ur,tree[p].rson);
        push_up(p);
    }
    inline int query(int l,int r,int ux,int p){
        if(!p)return 0;
        if(l>=ux&&r<=ux)return tree[p].val;
        spread(p,l,r);
        int mid=l+r>>1;
        int ans=0;
        if(ux<=mid)return query(l,mid,ux,tree[p].lson);
        else return query(mid+1,r,ux,tree[p].rson);
    }
}ST;
signed main(){
    scanf("%d%d%d",&n,&c,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&col[i]);
        loc[i]=last[col[i]];
        last[col[i]]=i;//花的顺序不会变，就地预处理。
    }
    for(int i=1,l,r;i<=m;i++){
        scanf("%d%d",&l,&r);
        q[i].l=l,q[i].r=r;q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    int tmp=1;
    for(int i=1;i<=n;i++){
        if(loc[i])ST.update(1,n,1,loc[loc[i]]+1,loc[i],ST.root);//能更新就更新
        while(q[tmp].r==i&&tmp<=m){
            ans[q[tmp].id]=ST.query(1,n,q[tmp].l,ST.root);
            ++tmp;//排好序后线性处理询问，我们只需要知道l点能采多少即可。 
        }
        if(tmp>m)break;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

线段树合并

顾名思义，就是把两棵线段树合并一棵线段树，保留或合并两棵树已有的数据（如果有可加性的话），这颗线段树的节点信息，编号等都由先前两棵树得来。

这个东西的全名叫动态开点权值线段树合并。也就是缝合了前面提到的两者的一种操作。

对于两棵待合并的线段树 A,B，合并操作实现如下：

• 处理节点问题。由于都是动态开点线段树，所以可能出现 A 树有节点 p 而 B 树没有的情况。如果有一棵树没有该节点，就将另一棵树的节点编号赋值给新树。
• 处理信息问题。在当前两棵树完成节点合并后使用 push_up 操作统一信息。
• 操作是递归实现的，完成合并后返回合并好的节点编号供上一级节点使用。

    int merge(int x,int y){
        if(!x)return y;
        if(!y)return x;
        ls(x)=merge(ls(x),ls(y));
        rs(x)=merge(rs(x),rs(y));//合并节点编号
        push_up(x);//合并节点信息
        return x;//返回合并好的节点编号，与无注释两行同作用。
    }

例题

不妨让权值线段树维护：当前节点的子树中有多少节点权值比它大。叶子节点存的是当前元素有多少个，query时直接扫数量即可。

然而影响当前节点答案的是它的子树。我们要先对树结构进行 dfs ，退出当前节点时合并他自己以及他的所有子节点，就地统计答案后方能得到“自己的子树中有多少大于它权值的点”。

void dfs(int u,int fa){
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(v==fa)continue;
        dfs(v,u);
        rt[u]=ST.merge(rt[u],rt[v]);
    }
    ans[u]=ST.query(1,n,val[u]+1,rt[u]);//query为查询有多少点权大于等于当前点。这是权值线段树，直接看节点val[u]右侧节点值之和即可。
    //由上文策略，退出当前节点时统计一下线段树中有多少点大于自己。
    //之后本节点会作为子节点合并到他的父节点，统计父节点时再用。
}

但是这个数据太大了得先离散化。

int n;
struct node{
    int v,id;
}vaL[MAXN];
bool cmp(node a,node b){
    return a.v<b.v;
}
int val[MAXN],rt[MAXN];
map<int,int>nti;
int itn[MAXN],tmp;

...

int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&vaL[i].v),val[i]=vaL[i].v,vaL[i].id=i;
    sort(vaL+1,vaL+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(!nti[vaL[i].v])nti[vaL[i].v]=++tmp,itn[tmp]=vaL[i].v;
        val[vaL[i].id]=nti[vaL[i].v];
    }
//网上好多是lowerbound和unique离散化，看不懂就先不这么用了。

由于线段树合并要求的是动态开点的权值线段树，故上传操作如下：

    void update(int l,int r,int k,int &p){
        if(!p)p=++tot;//没有当前节点或者儿子时先开点。
        if(l==r){//到达叶子节点后维护当前元素有多少个。
            ++tree[p].val;
            return;
        }
        int mid=l+r>>1;//没有到达叶子节点时维护当前区间内有多少元素
        if(k<=mid)update(l,mid,k,ls(p));//出于&p的设定，赋值儿子节点编号是顺带的。
        else update(mid+1,r,k,rs(p));
        push_up(p);
    }
                                 ...
signed main(){
...
    for(int i=2,fa;i<=n;i++){
        scanf("%lld",&fa);
        edge[fa].push_back(i);
        edge[i].push_back(fa);//建图，给dfs跑。
    }
    for(int i=1;i<=n;i++)ST.update(1,n,val[i],rt[i]);//出于&p的设定，赋值当前点在线段树中的实际点编号也是顺带的。
    ...

    return 0;                                 
}

然后是查询与合并操作。

    int query(int l,int r,int x,int p){//元素值为(l,r)的区间中有多少是大于等于x的？
        if(!p)return 0;//要查询的节点是开过的点，没开过的就返回0
        if(l>=x)return tree[p].val;//当前节点区间左端点值已经大于x了。
        //权值线段树中节点编号直接反应权值大小。直接加上整个节点的数目。
        int res=0;
        int mid=l+r>>1;
        if(mid>=x)res+=query(l,mid,x,ls(p));//x卡在半区间左侧，说明(l,mid)内也有可能有大于等于x的元素存在。
        res+=query(mid+1,r,x,rs(p));//找右半区间有多少大于等于x的节点。

        //因而查询区间被分割为：完全大于x的区间，可能大于x的区间。
        //可能大于x的区间最终会因为二分值mid而被完全分割成完全大于x的小段。
        return res;
    }
    int merge(int x,int y){//线段树合并操作，上文就是从这里复制的。
        if(!x)return y;
        if(!y)return x;
        ls(x)=merge(ls(x),ls(y));
        rs(x)=merge(rs(x),rs(y));
        push_up(x);
        return x;
    }

大概就是这样了。放一下总代码水字数。

#include<bits/stdc++.h>
#define int long long
#define MAXN 100005
using namespace std;
int n;
struct node{
    int v,id;
}vaL[MAXN];
bool cmp(node a,node b){
    return a.v<b.v;
}
int val[MAXN],rt[MAXN];
map<int,int>nti;
int itn[MAXN],tmp;
vector<int>edge[MAXN];
struct Segment_Tree{
    #define ls(p) tree[p].lson
    #define rs(p) tree[p].rson
    #define push_up(p) tree[p].val=tree[ls(p)].val+tree[rs(p)].val
    int tot;
    struct TREE{
        int val;
        int lson,rson;
    }tree[MAXN*20];
    void update(int l,int r,int k,int &p){
        if(!p)p=++tot;
        if(l==r){
            ++tree[p].val;
            return;
        }
        int mid=l+r>>1;
        if(k<=mid)update(l,mid,k,ls(p));
        else update(mid+1,r,k,rs(p));
        push_up(p);
    }
    int query(int l,int r,int x,int p){
        if(!p)return 0;
        if(l>=x)return tree[p].val;
        int res=0;
        int mid=l+r>>1;
        if(mid>=x)res+=query(l,mid,x,ls(p));
        res+=query(mid+1,r,x,rs(p));
        return res;
    }
    int merge(int x,int y){
        if(!x)return y;
        if(!y)return x;
        ls(x)=merge(ls(x),ls(y));
        rs(x)=merge(rs(x),rs(y));
        push_up(x);
        return x;
    }
}ST;
int ans[MAXN];
void dfs(int u,int fa){
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(v==fa)continue;
        dfs(v,u);
        rt[u]=ST.merge(rt[u],rt[v]);
    }
    ans[u]=ST.query(1,n,val[u]+1,rt[u]);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&vaL[i].v),val[i]=vaL[i].v,vaL[i].id=i;
    sort(vaL+1,vaL+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(!nti[vaL[i].v])nti[vaL[i].v]=++tmp,itn[tmp]=vaL[i].v;
        val[vaL[i].id]=nti[vaL[i].v];
    }
    for(int i=2,fa;i<=n;i++){
        scanf("%lld",&fa);
        edge[fa].push_back(i);
        edge[i].push_back(fa);
    }
    for(int i=1;i<=n;i++)ST.update(1,n,val[i],rt[i]);
    dfs(1,0);
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}

最后只会留下一颗线段树。然这棵线段树集成了先前小树的各种节点。先前的小树也可以被理解为是“残破的”，因为只负责维护部分信息。也就是说整个 dfs 与合并过程都是建树过程。

本题中的查询操作对“线段树的残破性”是必须的。当前处理的节点对“残破性”的要求是：线段树只能维护他自己以及他的子节点。自始至终只来得及开一颗线段树，在合并过程中就满足了部分点的答案，进行更新即可。

为什么不用板题讲？

因为我用的网上的树剖+树上差分过的。

所以在这讲一下树上差分。

树上差分

最早的想法是靠板题学线段树合并。然而

刚学完树剖。树上路径修改状操作反正我是只会用树剖写的。

然后发现不会写，查看题解，确实有树剖写法，用到了树上差分。

树上差分就是序列上差分的扩展。

差分树上，节点 i 的值 a_i 反应的是点 i 的实际权值 val_i 与其父亲节点权值 val_{fa} 的权值差，因此，进行路径 (1,i) 的遍历并汇总即可还原节点 i。

进行路径遍历并汇总即可还原节点。这句话很重要，看不懂代码先想想明不明白这句话的意思。

完成剖分后，对于一条链的底端点的下一个点 x 与顶点 top。在当前路径上增加救济粮 k 可以理解为:

val[x]-=k;
val[top]+=k;

namespace HPD{
    void modify(int x,int y,int k){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            tags[dfn[top[x]]].push_back(k);//对链上的点打tag
            tags[dfn[x]+1].push_back(-k);//更新到点x，实际要更新dfn[x]+1这个点的差分值。
            x=father[top[x]]; 
        }
        if(dep[x]>dep[y])swap(x,y);
        tags[dfn[x]].push_back(k),tags[dfn[y]+1].push_back(-k);
    }
}

至于为什么要打tag,向量tag的具体意义：

题目中给出的操作是：给路径上放类型 z 的救济粮，然我们现在实现的是给路径上每个点权值加上 z。

但是我们忽略掉了剖分时的线段树的类型。

如果这是一棵权值线段树，“给节点权值加 z”这样的操作实际为：将权值 z 的个数 +1。

线段树叶子节点 p 是一个桶。对于叶子节点，tree[p].val 为第 p 种救济粮的个数。对于非叶子节点，tree[p].val 为 p 所管辖的第 (l,r) 类救济粮中最多个数的那个的个数，tree[p].res 则为最多个数救济粮的种类。由此写出线段树。

struct Segment_Tree{
    #define leftson(p) p<<1
    #define rightson(p) p<<1|1
    struct TREE{
        int l,r;
        int val,tag;
        int res;
    }tree[MAXN<<2];
    void push_up(int p){
        if(tree[leftson(p)].val>=tree[rightson(p)].val)tree[p].res=tree[leftson(p)].res,tree[p].val=tree[leftson(p)].val;//选举个数最多救济粮的信息并存储到父亲节点。
        else tree[p].res=tree[rightson(p)].res,tree[p].val=tree[rightson(p)].val;
    }
    void build(int l,int r,int p){
        tree[p].l=l,tree[p].r=r,tree[p].val=tree[p].tag=0;
        if(l==r){tree[p].res=l;return;}//初始化编号
        int mid=l+r>>1;
        build(l,mid,leftson(p));
        build(mid+1,r,rightson(p));
        push_up(p);
    }   
    void update(int x,int k,int p){//将第x种救济粮个数增加k
        if(tree[p].l==tree[p].r){
            tree[p].val+=k;
            tree[p].tag+=k;
            return;
        }
        int mid=tree[p].l+tree[p].r>>1;
        if(x<=mid)update(x,k,leftson(p));
        else update(x,k,rightson(p));
        push_up(p);
    }
}ST;

关于答案统计。

重链剖分是按照 dfn 建树的，因此还原节点时也用 dfn 统计。

    for(int i=1;i<=n;i++){
        for(int id=0;id<tags[i].size();id++){
            int num=tags[i][id];
            if(num>0)ST.update(num,1,1);
            else ST.update(-num,-1,1);
        }
        ans[rk[i]]=ST.tree[1].val?ST.tree[1].res:0;
    }

坑点：没事不要用父亲节点 u 表示公式，u 不止一个儿子因此其所属子树节点编号最高能到 dfn[v]-1，进而其子树大小 siz[u] \neq siz[v]+1

因为线段树还没有合并，所以 1\sim dfn[v] 等的遍历不会获得最终的节点个数。很有意思。

#include<bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;
int n,q;
vector<int>edge[MAXN];
struct node{
    int type;
    int x,y;
}wzw[MAXN];
int father[MAXN];
int getf(int x){
    if(father[x]==x)return x;
    else return father[x]=getf(father[x]);
}
int dfn[MAXN],siz[MAXN],tim,efa[MAXN];
void dfs(int u,int fa){
    dfn[u]=++tim;
    efa[u]=fa;
    siz[u]=1;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }   
}
int rt[MAXN];
struct Segment_Tree{
    #define ls(p) tree[p].lson
    #define rs(p) tree[p].rson
    #define push_up(p) tree[p].val=tree[ls(p)].val+tree[rs(p)].val
    int tot;
    struct TREE{
        int lson,rson;
        int val;
    }tree[MAXN*20];
    inline void update(int l,int r,int x,int &p){
        if(!p)p=++tot;
        if(l==r){
            ++tree[p].val;
            return;
        }
        int mid=l+r>>1;
        if(x<=mid)update(l,mid,x,ls(p));
        else update(mid+1,r,x,rs(p));
        push_up(p);
    }
    inline int query(int l,int r,int ul,int ur,int p){
        if(!p)return 0;
        if(l>=ul&&r<=ur)return tree[p].val;
        int mid=l+r>>1;
        int res=0;
        if(ul<=mid)res+=query(l,mid,ul,ur,ls(p));
        if(ur>mid)res+=query(mid+1,r,ul,ur,rs(p));
        return res;
    }
    inline int merge(int x,int y){
        if(!x)return y;
        if(!y)return x;
        ls(x)=merge(ls(x),ls(y));
        rs(x)=merge(rs(x),rs(y));
        push_up(x);
        return x;
    }
}ST;
signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)father[i]=i;
    for(int i=1,u,v;i<=q;i++){
        char opt;
        cin>>opt;
        if(opt=='A'){
            scanf("%lld%lld",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
            wzw[i].type=1;
            wzw[i].x=u,wzw[i].y=v;  
        }
        else{
            scanf("%lld%lld",&u,&v);
            wzw[i].x=u,wzw[i].y=v;
        }
    }
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,0);
    for(int i=1;i<=n;i++)ST.update(1,n,dfn[i],rt[i]);
    for(int i=1,opt,u,v;i<=q;i++){
        u=wzw[i].x,v=wzw[i].y,opt=wzw[i].type;
        if(opt){
            u=getf(u),v=getf(v);
            father[v]=u;
            rt[u]=ST.merge(rt[u],rt[v]);
        }
        else{
            if(v==efa[u])swap(u,v);
            int fx=getf(u),fy=getf(v);
            int val1=ST.query(1,n,dfn[v],dfn[v]+siz[v]-1,rt[fx]);
            int val2=ST.query(1,n,1,dfn[v]-1,rt[fx])+ST.query(1,n,dfn[v]+siz[v],n,rt[fx]);
        //  printf("%lld %lld\n",val1,val2);
            printf("%lld\n",val1*val2);
        }
    }
    return 0;
}

实力足够后会添加：线段树合并 维护 dp