【LNOI 2014】 LCA

【题目链接】

点击打开链接

【算法】

考虑求lca(x,y)的深度

我们可以将从根到x路径上的点都打上标记，然后，询问y到根上路径的权值和

那么，求sigma(depth(lca(i,z)))（l <= i <= r )，我们可以将区间[l,r]中的点依次打上标记，然后，询问点z到根路径

上的权值和

因为此题有多组询问，显然在线很难做，因此，我们考虑离线计算答案

求sigma(depth(lca(i,z))) (l <= i <= r)，我们可以转化为

sigma(depth(lca(i,z))) ( 0 <= i <= r) - sigma(depth(lca(i,z))) (0 <= i <= l - 1)

那么，树链剖分/动态树都可以解决这道题，树链剖分的时间复杂度是O((n + q) log(n)^2)的，而动态树的时间复杂度是 O((n + q) log(n))的

【代码】

由于笔者太弱，不会动态树，所以这份代码是树链剖分的写法

#include<bits/stdc++.h>

using namespace std;

#define MAXM 50010

const int P = ;

struct Edge

{

    int to,nxt;

} e[MAXM];

struct Query

{

    int pos,opt,z,id;

} q[MAXM*];

int i,n,m,f,timer,tot,cnt,now,l,r,z;

int dfn[MAXM],size[MAXM],top[MAXM],head[MAXM],son[MAXM],ans[MAXM],fa[MAXM];

struct SegmentTree

{

        struct Node

        {

                int l,r;

                int sum,tag;

        } Tree[MAXM*];

        inline void build(int index,int l,int r)

        {

                int mid;

                Tree[index].l = l; Tree[index].r = r;

                Tree[index].sum = Tree[index].tag = ;

                if (l == r) return;

                mid = (l + r) >> ;

                build(index<<,l,mid);

                build(index<<|,mid+,r);

        }

        inline void pushdown(int index)

        {

                int l = Tree[index].l,r = Tree[index].r;

                int mid = (l + r) >> ;

                if (Tree[index].tag)

                {

                        Tree[index<<].sum = (Tree[index<<].sum + (mid - l + ) * Tree[index].tag) % P;

                        Tree[index<<|].sum = (Tree[index<<|].sum + (r - mid) * Tree[index].tag) % P;

                        Tree[index<<].tag = (Tree[index<<].tag + Tree[index].tag) % P;

                        Tree[index<<|].tag = (Tree[index<<|].tag + Tree[index].tag) % P;

                        Tree[index].tag = ;

                }

        }

        inline void update(int index)

        {

                Tree[index].sum = (Tree[index<<].sum + Tree[index<<|].sum) % P;

        }

        inline void modify(int index,int l,int r,int val)

        {

                int mid;

                if (Tree[index].l == l && Tree[index].r == r)

                {

                        Tree[index].sum = (Tree[index].sum + (r - l + ) * val) % P;

                        Tree[index].tag = (Tree[index].tag + val) % P;

                        return;

                }

                pushdown(index);

                mid = (Tree[index].l + Tree[index].r) >> ;

                if (mid >= r) modify(index<<,l,r,val);

                else if (mid +  <= l) modify(index<<|,l,r,val);

                else

                {

                        modify(index<<,l,mid,val);

                        modify(index<<|,mid+,r,val);

                }

                update(index);

        }

        inline int query(int index,int l,int r)

        {

                int mid;

                if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum;

                pushdown(index);

                mid = (Tree[index].l + Tree[index].r) >> ;

                if (mid >= r) return query(index<<,l,r);

                else if (mid +  <= l) return query(index<<|,l,r);

                else return (query(index<<,l,mid) + query(index<<|,mid+,r)) % P;

        }

} T;

inline bool cmp(Query a,Query b)

{

    return a.pos < b.pos;

}

inline void add(int u,int v)

{

        tot++;

        e[tot] = (Edge){v,head[u]};

        head[u] = tot;

}

inline void dfs1(int u)

{

        int i,v;

        size[u] = ;

        for (i = head[u]; i; i = e[i].nxt)

        {

                v = e[i].to;

                dfs1(v);

                size[u] += size[v];

                if (size[v] > size[son[u]] || !son[u]) son[u] = v;

        }

}

inline void dfs2(int u,int tp)

{

        int i,v;

        top[u] = tp;

        dfn[u] = ++timer;

        if (son[u]) dfs2(son[u],tp);

        for (i = head[u]; i; i = e[i].nxt)

        {

                v = e[i].to;

                if (son[u] != v) dfs2(v,v);

        }

}

inline void modify(int pos)

{

        int tp = top[pos];

        while (tp)

        {

                T.modify(,dfn[tp],dfn[pos],);

                pos = fa[tp]; tp = top[pos];

        }

        T.modify(,,dfn[pos],);

}

inline int query(int pos)

{

        int tp = top[pos],ans = ;

        while (tp)

        {

                ans = (ans + T.query(,dfn[tp],dfn[pos])) % P;

                pos = fa[tp]; tp = top[pos];

        }

        ans = (ans + T.query(,,dfn[pos])) % P;

        return ans;

}

int main()

{

        scanf("%d%d",&n,&m);

        for (i = ; i < n; i++)

        {

                scanf("%d",&fa[i]);

                add(fa[i],i);

        }

        dfs1();

        dfs2(,);

        T.build(,,timer);

        for (i = ; i <= m; i++)

        {

                scanf("%d%d%d",&l,&r,&z);

                if (l != ) q[++cnt] = (Query){l-,-,z,i};

                q[++cnt] = (Query){r,,z,i};

        }

        sort(q+,q+cnt+,cmp);

        now = -;

        for (i = ; i <= cnt; i++)

        {

                while (now +  <= q[i].pos)

                {

                        now++;

                        modify(now);

                }

                if (q[i].opt == ) ans[q[i].id] = (ans[q[i].id] + query(q[i].z)) % P;

                else ans[q[i].id] = (ans[q[i].id] - query(q[i].z) + P) % P;

        }

        for (i = ; i <= m; i++) printf("%d\n",ans[i]);

        return ;

}

巴特西

【LNOI 2014】 LCA

最新文章

热门文章