zcmimi's blog
avatar
zcmimi
2020-01-02

形态: 在一棵树上加多一条边

实现:

找出环后一次处理环上每个点的子树,然后再处理环

[IOI 2008]Island(求基环树直径)

IOI 2008 Island

先找出环,把环当根节点,找出每棵子树的直径和最大深度d_x

接着就要在环上找到两点x,y使d_x+dis(x,y)+d_y最大

可以破环后用单调队列\mathcal O(n)处理

#include<cstdio>
const int N=1000011;
#define ll long long
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
inline ll max(ll x,ll y){return x>y?x:y;}
int n,cnt=0,head[N],dfn[N],sz=0,pre[N],tt[N],tot=0,q[N];
bool b[N];
struct edge{
    int to,nxt,w;
}e[N<<1];
void add(int x,int y,int w){
    e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;e[cnt].w=w;
}
void dfs(int x){
    dfn[x]=++sz;
    fl(i,x)if(to!=pre[x]){
        if(dfn[to]){
            if(dfn[to]<dfn[x])continue;
            b[tt[++tot]=x]=1;
            for(int y=to;y!=x;y=pre[y])b[tt[++tot]=y]=1;
        }
        else pre[to]=x,dfs(to);
    }
}
ll f[N],d[N],s[N],ans=0;
void dp(int x,int fa){
    fl(i,x)if(to!=fa&&!b[to]){
        dp(to,x);
        f[x]=max(f[x],max(f[to],d[x]+d[to]+e[i].w));
        d[x]=max(d[x],d[to]+e[i].w);
    }
}
void work(int x){
    ll tmp=0;
    tot=0;
    dfs(x);
    tt[tot+1]=tt[1];
    int p=0;
    for(int i=1;i<=tot;++i)
        fl(j,tt[i])if(to==tt[i+1])
            s[++p]=e[j].w;
    for(int i=1;i<=tot+1;++i)
        tt[i+tot]=tt[i],s[i+tot]=s[i];
    for(int i=2;i<=tot*2;++i)s[i]+=s[i-1];
    for(int i=1;i<=tot;++i)dp(tt[i],0),tmp=max(tmp,max(f[tt[i]],d[tt[i]]));
    int h=1,t=0;
    for(int i=1;i<=tot*2;++i){
        while(h<=t&&i-q[h]>=tot)++h;
        if(h<=t)tmp=max(tmp,d[tt[i]]+d[tt[q[h]]]+s[i-1]-s[q[h]-1]);
        while(h<=t&&d[tt[i]]-s[i-1]>=d[tt[q[t]]]-s[q[t]-1])--t;
        q[++t]=i;
    }
    ans+=tmp;
}
int main(){
    scanf("%d",&n);
    int y,w;
    for(int i=1;i<=n;++i)
        scanf("%d%d",&y,&w),
        add(i,y,w),add(y,i,w);
    for(int i=1;i<=n;++i)if(!dfn[i])work(i);
    printf("%lld\n",ans);
}

创世纪(基环树dp)

创世纪

两次dp解决代替基环树dp

所有的A_i\rightarrow i构成了一棵基环树

我们先考虑如果基环树的子树怎么做

也就是树型dp

(f_x表示不放,g_x表示放)

若元素i不投放,

f_x=\sum_{A_y=x}\max(f_y,g_y)

否则必须至少有一个元素限制i,不能投放

g_x=\max_{A_y=x}\{f_y+\sum_{A_z=x,z\not = y}\max(f_z,g_z)\}

找到环上的一个点,将它和它限制的那个点断开,先后进行两次树形dp,

第一次是假设环上的这个点对其限制的点不起限制作用

另外一次是强制环上那个点已经限制了其可以限制的点(也就是环上那个点不选)

#include<cstdio>
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
const int N=1000011;
int n,cnt=0,head[N],A[N],f[N],g[N],RT;
struct edge{
    int to,nxt;
}e[N<<1];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
bool v[N];
void dp(int x){
    v[x]=1;f[x]=0;
    int res=1<<30;
    fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    if(to!=RT){
        dp(to);
        f[x]+=max(f[to],g[to]);
        res=min(res,max(g[to]-f[to],0));
    }
    g[x]=f[x]+1-res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",A+i),add(A[i],i);
    int ans=0;
    for(int i=1;i<=n;++i)
    if(!v[i]){
        int res=0;
        RT=i;
        while(!v[A[RT]]){
            v[RT]=1;
            RT=A[RT];
        }
        dp(RT);
        res=max(f[RT],g[RT]);
        RT=A[RT];
        dp(RT);
        ans+=max(res,max(f[RT],g[RT]));
    }
    printf("%d\n",ans);
}

[ZJOI2008]骑士(基环树dp)

将一个骑士与他最痛恨的人连边

先考虑这个如果是树型dp:

f_x表示不取x,g_x表示取x

f_x=\sum \max(f_{to},g_{to}) \\ g_x=\sum f_{to}

我们可以用两次树型dp代替基环树dp

第一次: 选择x,不选择x最痛恨的人

第一次: 选择x最痛恨的人,不选择x

#include<cstdio>
int max(int x,int y){return x>y?x:y;}
const int N=1000011;
int n,cnt=0,head[N],val[N],a[N],rt;
long long f[N],g[N],ans=0,res,inf=1ll<<60;
struct edge{
    int to,nxt;
}e[N<<1];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
bool v[N];
void dp(int x){
    f[x]=0;g[x]=val[x];
    v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    if(to!=rt){
        dp(to);
        f[x]+=max(f[to],g[to]);
        g[x]+=f[to];
    }
    else g[to]=-inf;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",val+i,a+i),add(a[i],i);
    for(int i=1;i<=n;++i)
    if(!v[i]){
        rt=i;
        res=0;
        while(!v[a[rt]]){
            v[rt]=1;
            rt=a[rt];
        }
        dp(rt);//强制选i
        res=max(f[rt],g[rt]);
        rt=a[rt];
        dp(rt);//强制选a[i]
        ans+=max(res,max(f[rt],g[rt]));
    }
    printf("%lld\n",ans);
}
基环树
comment评论
Search
search