Split The Tree – HDU6054 – dfs序+主席树

题目链接

https://cn.vjudge.net/problem/HDU-6504

题目大意

一棵树,每个节点有一个权值,树的权值是节点不同权值的数量,问在只切断一条边的情况下所能得到的最大权值是多少。

解题思路

dfs序加主席树
首先用dfs序处理,主席树求树上不同点个数就是对于每个版本的主席树,都只维护值最后出现的位置,这样想求l-r的区间内不同数的个数就可以用r那个版本的主席树去查l-r的结果了。
但是当割断一条边后,很有可能会出现这种情况

途中灰色的是切下来的子树,可以通过第r个版本的主席树快速的查询,但是对于剩下的那棵大树,也就是图中黄色的那一部分,被分成了两部分,无法得到他们中不同数的个数。
所以需要把树复读一下。

这里黄色的部分就等于上面黄色的两部分,由于现在他们连续了所以也可以用主席树直接求解了。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+7;
int head[N],val[N],mp[N];
int cnt;
struct Edge{
    int u,v,nxt;
}edge[N*2];
void add(int u,int v) {
    edge[++cnt]= {u,v,head[u]};
    head[u]=cnt;
    edge[++cnt]= {v,u,head[v]};
    head[v]=cnt;
}
int cur,dd[N],le[N],ri[N];
void dfs(int u,int f){
    dd[++cur]=u;
    le[u]=cur;
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==f)continue;
        dfs(v,u);
    }
    ri[u]=cur;
}
int rt[N],t[N*40],ls[N*40],rs[N*40],tot;
int build(int l,int r){
    int now=++tot;
    t[now]=0;
    if(l==r)return now;
    int m=(l+r)>>1;
    ls[now]=build(l,m);
    rs[now]=build(m+1,r);
    return now;
}
int updata(int o,int l,int r,int p,int v){
    int now=++tot;
    t[now]=t[o]+v;
    if(l==r)return now;
    ls[now]=ls[o];
    rs[now]=rs[o];
    int mid=l+r>>1;
    if(p<=mid)ls[now]=updata(ls[o],l,mid,p,v);
    else rs[now]=updata(rs[o],mid+1,r,p,v);
    return now;
}
int query(int o,int p,int l,int r){
    if(l==r)return t[o];
    int mid=l+r>>1;
    int res=0;
    if(p<=mid)return query(ls[o],p,l,mid)+t[rs[o]];
    return query(rs[o],p,mid+1,r);
    return res;
}
int main() {
    int n,x;
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++) {
            head[i]=-1;
        }
        cnt=-1;
        tot=cur=0;
        for(int i=2; i<=n; i++) {
            scanf("%d",&x);
            add(i,x);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&val[i]);
            mp[val[i]]=0;
        }
        dfs(1,0);
        for(int i=n+1;i<=2*n;i++){
            dd[i]=dd[i-n];
        }
        rt[0]=build(1,N);
        for(int i=1;i<=2*n;i++){
            int u=dd[i];
            if(mp[val[u]]){
                rt[i]=updata(rt[i-1],1,N,mp[val[u]],-1);
                rt[i]=updata(rt[i],1,N,i,1);
            }
            else{
                rt[i]=updata(rt[i-1],1,N,i,1);
            }
            mp[val[u]]=i;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            int tmp=query(rt[ri[i]],le[i],1,N);
            tmp+=query(rt[le[i]+n-1],ri[i]+1,1,N);
            ans=max(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注