请求加入树状数组、差分的tag

Zhangikun @ 2023-10-23 13:40:26

by Elairin176 @ 2023-10-23 21:51:08

@Zhangikun 您读题了吗。本题显然是区间查询。

by Zhangikun @ 2023-10-24 08:48:00

@Eirin_Yagokoro 您读题了吗？

• 将两个节点之间的路径上的边的权值均加一（显然区间修改吧）。

• 查询两个节点之间的那一条边的权值，保证两个节点直接相连（只查询一条边，显然单点求值）。

树状树组+差分AC代码：

#include<bits/stdc++.h>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std;
const int cxk=1e5+5;
int n,m,sz[cxk],fa[cxk],upp[cxk],dep[cxk],top[cxk],dfn[cxk],tot,tree[cxk],pt[cxk];
vector<int>nbr[cxk];
void dfs(int cur)
{
    dep[cur]=dep[fa[cur]]+1;
    sz[cur]=1;
    int maxi=0;
    for(int nxt:nbr[cur])
    {
        if(nxt==fa[cur])
            continue;
        fa[nxt]=cur;
        dfs(nxt);
        sz[cur]+=sz[nxt];
        if(maxi<sz[nxt])
        {
            maxi=sz[nxt];
            upp[cur]=nxt;
        }
    }
}
void dfs2(int cur)
{
    dfn[cur]=++tot;
    if(upp[cur]==0)
        return; 
    top[upp[cur]]=top[cur];
    dfs2(upp[cur]);
    for(int nxt:nbr[cur])
    {
        if(nxt==fa[cur]||nxt==upp[cur])
            continue;
        top[nxt]=nxt;
        dfs2(nxt);
    }
}
//---------------------------------------
void update2(int x,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=val;
}
int query(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
        sum+=tree[i];
    return sum;
}
//---------------------------------------
void update(int x,int y)
{
    int tx=top[x],ty=top[y];
    while(tx!=ty)//保证不在同一条链
    {
        if(dep[tx]<dep[ty])
        {
            swap(tx,ty);
            swap(x,y);
        }
        update2(dfn[tx],1);
        update2(dfn[x]+1,-1);
        x=fa[tx],tx=top[x];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    update2(dfn[x]+1,1);
    update2(dfn[y]+1,-1);
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1,x,y;i<n;i++)
    {
        cin>>x>>y;
        nbr[x].push_back(y);
        nbr[y].push_back(x);
    }
    top[1]=1;
    dfs(1);
    dfs2(1);
    char opt;
    for(int u,v;m--;)
    {
        cin>>opt>>u>>v;
        if(opt=='Q')
        {
            if(dep[u]<dep[v])
                swap(u,v);
            cout<<query(dfn[u])<<"\n";
        }
        else
            update(u,v);
    }
}

AC记录

by Elairin176 @ 2023-10-24 18:58:05

@Zhangikun 哦哦没有看到，抱歉
昨晚刚用树剖 AC 了，还以为是像板子一样的查询

by FstAutoMaton @ 2023-11-04 11:54:52

@Zhangikun tlqtj？？？