题解 P3459 【[POI2007]MEG-Megalopolis】

2017-09-28 15:55:47


【POI补全计划#43 POI2007 MEG】

我们来尝试暴力一点的做法:树剖

基本上就是无脑搞,将问题转换为:

维护树上两个操作

1.树上单条边权-1

2.查询树上点到根路径上权值和

就当是用作树链剖分模板题了

P.S.单点修改链上查询一般可以转化为dfs序,而且dfs序常数一般比树链剖分小(楼下的解法)

贴代码

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int MAXN=250010;
struct node
{
    int l,r,sum;
    node *lson,*rson;
}*root,pool[MAXN*4];
int top;
node* build(int l,int r)
{
    node *tmp=&pool[++top];
    tmp->l=l;tmp->r=r;
    tmp->sum=r-l+1;
    if(l!=r)
    {
        int mid=(l+r)/2;
        tmp->lson=build(l,mid);
        tmp->rson=build(mid+1,r);
    }
    return tmp;
}
void change(node *cur,int pos)//minus 1
{
    cur->sum--;
    if(cur->l==cur->r)return;
    if(cur->lson->r>=pos)change(cur->lson,pos);
    else change(cur->rson,pos);
}
int query(node *cur,int l,int r)
{
    if(cur->l==l&&cur->r==r)
        return cur->sum;
    if(cur->lson->r>=r)return query(cur->lson,l,r);
    else if(cur->rson->l<=l)return query(cur->rson,l,r);
    else return query(cur->lson,l,cur->lson->r)+query(cur->rson,cur->rson->l,r);
}
struct edge
{
    int v,id;
    edge *next;
}*h[MAXN],epool[MAXN*2];
int etop;
inline void addedge(int u,int v)
{
    edge *tmp=&epool[++etop];tmp->v=v;tmp->next=h[u];h[u]=tmp;
    edge *pmt=&epool[++etop];pmt->v=u;pmt->next=h[v];h[v]=pmt;
}
int dep[MAXN],siz[MAXN],pa[MAXN],maxson[MAXN],paedge[MAXN],pathroot[MAXN];
void dfs1(int u)
{
    siz[u]=1;
    for(edge *tmp=h[u];tmp;tmp=tmp->next)
    {
        if(!dep[tmp->v])
        {
            dep[tmp->v]=dep[u]+1;
            pa[tmp->v]=u;
            dfs1(tmp->v);
            siz[u]+=siz[tmp->v];
            if(siz[tmp->v]>siz[maxson[u]])maxson[u]=tmp->v;
        }
    }
}
int cur;
void dfs2(int u)
{
    if(maxson[u])
    {
        paedge[maxson[u]]=++cur;
        pathroot[maxson[u]]=pathroot[u];
        dfs2(maxson[u]);
    }
    for(edge *tmp=h[u];tmp;tmp=tmp->next)
    {
        if(tmp->v!=maxson[u]&&dep[tmp->v]==dep[u]+1)
        {
            paedge[tmp->v]=++cur;
            pathroot[tmp->v]=tmp->v;
            dfs2(tmp->v);
        }
    }
}
inline int qtree(int x)
{
    int ans=0;
    while(x)
    {
        ans+=query(root,paedge[pathroot[x]],paedge[x]);
        x=pa[pathroot[x]];
    }
    return ans;
}
int main()
{
    int n,q,a,b;
    char ch;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
    }
    dep[1]=1;
    dfs1(1);
    pathroot[1]=1;
    dfs2(1);
    root=build(0,n-1);
    scanf("%d",&q);
    for(int i=1;i<=n+q-1;i++)
    {
        scanf(" %c",&ch);
        if(ch=='W')
        {
            scanf("%d",&a);
            printf("%d\n",qtree(a)-1);
        }
        else
        {
            scanf("%d%d",&a,&b);
            change(root,paedge[b]);
        }
    }
    return 0;
}