[题解] gdfzoj 733 | 2020提高训练9T1

传送门

原题(我赛后才知道的）

知识点：主席树，LCA

题目大意：给定树上两点 x,y ，求 x 到 y 的简单路径上权值在 l,r 之间的数的和

看到题目，首先可以想到权值主席树，将每个节点至根节点这一条链上的节点信息存下来

对于节点 u ,可以从他的父亲节点处更新

然后用 LCA 解决

要点：

1.坐标需要离散化

2.主席树码量较大，调试需要耐心

3.LCA最好用tarjan求，不要用倍增，不然容易MLE（不要问我怎么知道的）

代码：

#include<bits/stdc++.h>
namespace my_std
{
    using namespace std;
    #define int long long
    #define rep(i,a,b) for (int i=(a);i<=(b);i++)
    #define drep(i,a,b) for (int i=(a);i>=(b);i--)
    #define go(u) for (int i=head[(u)];i;i=e[i].nxt)
    #define pf printf
    #define writeln(x) write(x),putchar('\n')
    #define writesp(x) write(x),putchar(' ')
    #define mem(x,v) memset(x,v,sizeof(x))
    typedef long long ll;
    const int INF=0x7fffffff;
    inline int read()
    {
        int sum=0,f=1;
        char c=0;
        while (!isdigit(c))
        {
            if (c=='-') f=-1;
            c=getchar();
        }
        while (isdigit(c))
        {
            sum=(sum<<1)+(sum<<3)+(c^48);
            c=getchar();
        }
        return sum*f;
    }
    void write(int k)
    {
        if (k<0) putchar('-'),k=-k;
        if (k>=10) write(k/10);
        putchar(k%10+'0');
    }
}
using namespace my_std;
const int N=100010;
struct Tree
{
    struct point
    {
        int l,r,val;
    }tree[N*18];
    int cnt=0,T[N];
    inline void push_up(int node)
    {
        tree[node].val=tree[tree[node].l].val+tree[tree[node].r].val;
    }
    inline int clone(int node)
    {
        tree[++cnt]=tree[node];
        return cnt;
    }
    void build(int &node,int start,int end)
    {
        node=++cnt;
        if (start==end) return;
        int mid=(start+end)>>1;
        build(tree[node].l,start,mid);
        build(tree[node].r,mid+1,end);
    }
    void update(int &node,int last,int start,int end,int p,int val)
    {
        node=clone(last);
        tree[node].val+=val;
        if (start==end) return;
        int mid=(start+end)>>1;
        if (p<=mid) update(tree[node].l,tree[last].l,start,mid,p,val);
        else update(tree[node].r,tree[last].r,mid+1,end,p,val);
    }
    int query(int node,int start,int end,int l,int r)
    {
        if (start>r||end<l) return 0;
        if (start>=l&&end<=r) return tree[node].val;
        int mid=(start+end)>>1;
        int sum_left=query(tree[node].l,start,mid,l,r);
        int sum_right=query(tree[node].r,mid+1,end,l,r);
        return sum_left+sum_right;
    }
}tree;
struct edge
{
    int to,nxt;
}e[N<<1];
struct qedge
{
    int to,nxt,lca;
}qe[N<<1];
int n,m,t,cnt,qcnt=1,head[N],qhead[N],fa[N];
int a[N],val[N];
inline void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void addq(int u,int v)
{
    qe[++qcnt].to=v;
    qe[qcnt].nxt=qhead[u];
    qhead[u]=qcnt;
}
struct Query
{
    int u,v,l,r;
    void get()
    {
        u=read(),v=read(),l=read(),r=read();
        addq(u,v),addq(v,u);
    }
}p[N];
bool vis[N];
int f[N];
inline int getfa(int x)
{
    if (fa[x]==x) return x;
    return fa[x]=getfa(fa[x]);
}
void tarjan(int u)
{
    vis[u]=1;
    fa[u]=u;
    go(u)
    {
        int v=e[i].to;
        if (vis[v])
        {
            f[u]=v;
            continue;
        }
        tarjan(v);
        fa[v]=u;
    }
    for (int i=qhead[u];i;i=qe[i].nxt)
    {
        int v=qe[i].to;
        if (vis[v])
        {
            qe[i].lca=getfa(v);
            qe[i^1].lca=qe[i].lca;
        }
    }
}
void get_tree(int u,int fa)
{
    tree.update(tree.T[u],tree.T[fa],1,t,a[u],val[a[u]]);
    go(u)
    {
        int v=e[i].to;
        if (v==fa) continue;
        get_tree(v,u);
    }
}
inline void solve(int x,int y,int LCA,int l,int r)
{
    int tmp1=tree.query(tree.T[x],1,t,l,r);
    int tmp2=tree.query(tree.T[y],1,t,l,r);
    int tmp3=tree.query(tree.T[LCA],1,t,l,r);
    int tmp4=tree.query(tree.T[f[LCA]],1,t,l,r);
    writesp(tmp1+tmp2-tmp3-tmp4);
}
signed main()
{
    n=read();m=read();
    rep(i,1,n) a[i]=val[i]=read();
    rep(i,1,n-1)
    {
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    sort(val+1,val+n+1);
    t=unique(val+1,val+n+1)-val-1;
    rep(i,1,n) a[i]=upper_bound(val+1,val+t+1,a[i])-val-1;
    get_tree(1,0);
    rep(i,1,m) p[i].get();
    tarjan(1);
    rep(i,1,m)
    {
        int u=p[i].u,v=p[i].v,l=p[i].l,r=p[i].r;
        int lca=qe[i<<1].lca;
        l=lower_bound(val+1,val+t+1,l)-val;
        r=upper_bound(val+1,val+t+1,r)-val-1;
        if (l>r)
        {
            writesp(0);
            continue;
        }
        solve(u,v,lca,l,r);
    }
}

备注：听 Frez 学长说因为此题离线，还可以将查询分成 0 至 r , 0 至 l-1 两部分，可以用线段树实现

我太菜了.jpg

[题解] gdfzoj 733 | 2020提高训练9T1

原文：https://www.cnblogs.com/ZHANG-SHENG-HAO/p/12514723.html