题解 P3038 【[USACO11DEC]牧草种植Grass Planting】

chen_zhe · 2017-07-15 20:03:11 · 题解

这道题目显然是一个树链剖分的模板题，但是我就来一发倍增lca加上树状数组的代码吧。

我们先dfs一发求出先序遍历，然后再进行lca的预处理。

对于种草的操作，对于l[u],l[v]是要加1的，对于l[lca(u,v)]要减去2，和区间覆盖问题类似。（说白了就是一个树上差分）

时间复杂度应该是O(n log n)，跑这个数据是可以接受的。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n,m,f[100050],time=0;

int depth[100050],r[100050],l[100050],fa[100050][21];

vector <int> graph[100050];

int Lowbit(int x)
{
    return x&-x;
}

void Change(int k,int num)
{
    while (k<=n)
    {
        f[k]+=num;
        k+=Lowbit(k);
    }
}

int Ask(int k)
{
    int ans=0;
    while (k>0)
    {
        ans+=f[k];
        k-=Lowbit(k);
    }
    return ans;
}

int lca(int u,int v)
{
    if (depth[u]<depth[v])
        swap(u,v);
    for (int k=20;k>=0;k--)
        if (depth[u]-depth[v]>=1<<k)
            u=fa[u][k];
    if (u==v)
        return u;
    for (int k=20;k>=0;k--)
        if (fa[u][k]!=fa[v][k])
        {
            u=fa[u][k];
            v=fa[v][k];
        }
    return fa[u][0];
}

void dfs(int u,int p)
{
    depth[u]=depth[p]+1;
    fa[u][0]=p;
    time++;
    l[u]=time;
    for (int i=0;i<graph[u].size();i++)
    {
        int v=graph[u][i];
        if (v!=p)
            dfs(v,u);
    }
    r[u]=time;
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1,0);
    for (int k=1;k<=20;k++)
        for (int u=1;u<=n;u++)
            fa[u][k]=fa[fa[u][k-1]][k-1];
    for (int i=1;i<=m;i++)
    {
        char chr;
        int u,v;
        scanf("%s%d%d",&chr,&u,&v);
        //cout << v << " " << l[v] << endl;
        if (chr=='P')
        {
            int p=lca(u,v);
            Change(l[u],1);
            Change(l[v],1);
            Change(l[p],-2);
        }
        else
        {
            if (depth[u]<depth[v])
                u=v;
            printf("%d\n",Ask(r[u])-Ask(l[u]-1));
        }
    }
    return 0;
}