noone___'s blog
0%

换根dp

发表于 更新于 分类于
继续复习，记性好差

理论

换根 $dp$ 通常在 不指定根节点，且根节点的不同对于所求值有影响时 使用

套路的，有以下步骤：

  • 任意的指定根节点
  • 对于当前的有根树，做一次树形 $dp$ ，并将状态转移到上面
  • 从第一次的根开始做 $dfs$ ,计算转移后的阶

例题

P6419 [COCI2014-2015#1] Kamp

一棵树上有 $K$ 个人集中在同一点，需要将这 $K$ 人分别送回，对于 $i=1\sim n$ ，如果集中在 $i$ 最少需要多少时间

题面描述并不是太清楚，但手玩样例会发现司机最后不需要返回到聚会点

  • $dfs1$

    考虑子树内的部分如何统计：设 $g_u$ 表示从 $u$ 点开始将 $u$ 子树内的人全部送回家并返回 $u$ 的方案数

    显然有 $g_u=\sum_{v\ is\ subtree\ of\ u} g_v+2\times w_{u,v}$

    再考虑到司机不需要回到出发点，那么最后的答案需要减去离聚会点距离最远的一个人的距离

    那么还需要存从当前点出发的最长链 $len_u$

  • $dfs2$

    从全局的考虑，设 $f_u$ 表示以点 $u$ 为聚会点送人并最后回到 $u$ 的最短距离，那么有：

    对于最长链，考虑在 $dfs1$ 中维护另一个次长链便于转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int N=5e5+100;
int n,K;
int head[N],tot,ver[N<<1],Next[N<<1],edge[N<<1];
int pos[N],num[N];//num是家在u子树内的人数
int len[N],id[N],se_len[N];//id_u 从u开始的最长链经过的第一个节点
ll g[N],f[N];

inline void add(int u,int v,int w){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=w;}

void dfs1(int x,int fa){
    if(pos[x]) num[x]=1;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i],w=edge[i]; if(y==fa)continue;
        dfs1(y,x);
        if(num[y]){
            g[x]+=g[y]+(ll) 2*w;
            rei now=len[y]+w;
            if(now>=len[x]) se_len[x]=len[x],len[x]=now,id[x]=y;
            else if(now>se_len[x]) se_len[x]=now;
        }
        num[x]+=num[y];
    }
}

void dfs2(int x,int fa){
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i],w=edge[i]; if(y==fa)continue;
        if(!num[y]) f[y]=f[x]+(ll) 2*w,len[y]=len[x]+w;
        else if(K-num[y]){
            f[y]=f[x];
            if(id[x]!=y && len[y]<len[x]+w) se_len[y]=len[y],len[y]=len[x]+w,id[y]=x;//x的最长链可以更新y
            else if(len[y]<se_len[x]+w) se_len[y]=len[y],len[y]=se_len[x]+w,id[y]=1;//x次长链可以
            else if(se_len[y]<len[x]+w && id[x]!=y) se_len[y]=len[x]+w;//x最长可以更新y次长
            else if(se_len[y]<se_len[x]+w) se_len[y]=se_len[x]+w;//x次长更新y次长
        }
        else f[y]=g[y];
        dfs2(y,x);
    }
}

int main(){
    scanf("%d%d",&n,&K);
    for(rei i=1,u,v,w;i<n;++i) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
    for(rei i=1,x;i<=K;++i) scanf("%d",&x),pos[x]=1;
    dfs1(1,0);
    f[1]=g[1];
    dfs2(1,0);
    for(rei i=1;i<=n;++i) printf("%lld\n",f[i]-len[i]);
    getchar(),getchar();
    return 0;
}

P3647 [APIO2014]连珠线

从一个珠子开始，每次可以用以下一种方式添加一个新珠子：用红线与一个珠子连起来；将两个被红线链接的珠子之间插入一个新珠子，并用蓝边链接两边两个

每条边有边权，得分是所有蓝线长度之和，只给出珠子和链的连接方式，但不告诉颜色，求最大可能得分

有一个结论是：蓝线中点的形式一定是形如 sonx-x-fax 而不是 sonx-x-sonx

先假定一个根，设 $f_{i,0/1}$ 表示点 $i$ 是否是蓝线中点，以 $i$ 为根的子树中得到的最大值

那么有转移：

再考虑如何换根：

当一个点的儿子变成父亲时：儿子的贡献消失，转移方程中的最大值可能不存在，所以记录次大值

设 $dp_{i,0/1,j}$ 表示 $f_{i,0/1}$ 统计中，不考虑第 $j$ 个儿子所得的答案，对于 $dp_{i,0,j}$ 直接减去，对于 $dp_{i,1,j}$ 用次大值维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
const int N=2e5+100;
const int INF=0x3f3f3f3f;
int n,ans;
int head[N],ver[N<<1],Next[N<<1],edge[N<<1],tot;
int par[N],len[N],f[N][2];//f_i,0/1:以i为根子树中，i是否作为蓝线中点得到的最大价值
vector<int> son[N],dp[N][2],Mx[N];//dp{i,0/1,j} 在f_{i,0/1} 状态中，不考虑第j个儿子所能得到的答案

inline void add(int u,int v,int val){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=val;}
inline int move(int x,int i){ return f[x][0]+edge[i]-max(f[x][0],f[x][1]+len[x]);}//状态转移

void dfs(int x,int fa){
    f[x][0]=0,f[x][1]=-INF;
    rei MAX=-INF,MAX_se=-INF;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fa) continue;
        len[y]=edge[i],par[y]=x;
        son[x].push_back(y);
        dfs(y,x);
        f[x][0]+=max(f[y][0],f[y][1]+edge[i]);
        rei tmp=move(y,i);
        if(tmp>MAX) MAX_se=MAX,MAX=tmp;
        else if(tmp>MAX_se) MAX_se=tmp;
    }
    f[x][1]=f[x][0]+MAX;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fa) continue;
        dp[x][0].push_back(f[x][0]-max(f[y][0],f[y][1]+edge[i]));
        if(move(y,i)==MAX){
            dp[x][1].push_back(dp[x][0].back()+MAX_se);
            Mx[x].push_back(MAX_se);
        }
        else{
            dp[x][1].push_back(dp[x][0].back()+MAX);
            Mx[x].push_back(MAX);
        }
    }
}

void dfs2(int x){
    for(rei i=0,SS=son[x].size()-1;i<=SS;++i){
        f[x][0]=dp[x][0][i],f[x][1]=dp[x][1][i];
        if(par[x]){
            f[x][0]+=max(f[ par[x] ][0],f[ par[x] ][1]+len[x]);
            f[x][1]=f[x][0]+max(Mx[x][i],f[ par[x] ][0]+len[x]-max(f[ par[x] ][0],f[ par[x] ][1]+len[x]));
        }
        ans=max(ans,f[ son[x][i] ][0]+max(f[x][0],f[x][1]+len[ son[x][i] ]));
        dfs2(son[x][i]);
    }
}

int main(){
    scanf("%d",&n);
    for(rei i=1,x,y,z;i<n;++i) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
    dfs(1,0); dfs2(1);
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

P4228 [清华集训2017] 榕树之心

起初时，树上只有一个点，心也在一号点，之后每一步树会长出一个新节点，心会沿着其到新节点的简单路径走一步，不同的生长顺序会时心最终位置不同，求哪些点可能时心最后在的位置

对于任意点 $x$ ，心最后在 $x$ 的必要条件为 $depth_x+n$ 是奇数

再考虑如何使心在根节点：显然当根的所有子树大小都小于 $\left\lfloor\frac{n}{2} \right\rfloor$ 时，心可能在根节点

那么当有一子树大小大于 $\left\lfloor\frac{n}{2} \right\rfloor$ 时，根可能被拉到该子树中，但也可能仍会在根节点中(例如当该子树是一个菊花图时)

考虑维护子树内 心的深度：设 $f_i$ 表示 $i$ 子树中，心与 $i$ 相对深度的最小值，显然 $f_i$ 与 $Size_i$ 始终具有不同的奇偶值

设 $i$ 的子树中子树大小最大的是 $c$ 子树，那么有：

  • 若 $Size_c\leq \left\lfloor\frac{Size_i}{2} \right\rfloor$

    则心可以被拉回，$f_i=(Size_i+1)\mod 2$

  • 否则

    心可能在 $c$ 子树中，设 $rest=Size_i-Size_c-1$

    若 $f_c\leq rest$ ，则心能拉回来，仍有 $f_i=(Size_i+1)\mod 2$

    若 $f_c>rest$ ，此时仍要尽力去拉，则有 $f_i=f_c-rest+1$

那么当 $f_0=1$ 时，心在根节点

再考虑换根过程：

对于每个点，先考虑 $depth_x+n$ 的奇偶性

对于根从 $1$ 转移到 $x$ 的情况，此时 $x$ 上方可以看成另一个子树

那么换根时，对于每个点 $x$ ，求出其上面的子树大小

与 $1$ 为根时类似的，考虑 $x$ 中 $\max\{Size_c\}$ 的子树 $c$ ，比较 $rest$ 与 $f_c$ 的关系即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
const int N=1e5+100;
int head[N],ver[N<<1],Next[N<<1],tot;
int n;
int fa[N],depth[N],Size[N];
int prf[N],sef[N],f[N];//f_i:以i为根的子树中，通过操作，心深度相对于i的最小值
//最大子树，次大子树
char ok[N];
bool only_root= getchar()==51;

inline void add(int u,int v){
    ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
}

inline void ups(int &x,const int y){
    Size[x]<Size[y] ? x=y : 0;
}

void dfs(int x){
    rei &fi=prf[x],&se=sef[x];
    Size[x]=fi=se=0;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fa[x]) continue;
        fa[y]=x, depth[y]=depth[x]+1, dfs(y), Size[x]+=Size[y];
        Size[fi]<Size[y] ? (se=fi,fi=y) : (ups(se,y),0);//注意这里ups没有返回值
    }
    f[x]=(f[fi]<=Size[x]-Size[fi] ? Size[x]&1/*在子树中，心相对深度取决于子树奇偶*/ : f[fi]-(Size[x]-Size[fi])+1);
    //是否是重子树 ？ 否：心可以被拉回来 ： 是：心可能在fi的子树中（注意相对深度
    ++Size[x];
}

void dfs2(int x,int g=0){//换根，考虑其他点能否为心
    rei y,fi;
    //显然有结论，depth(x)+n为奇数是x为心的必要条件
    rei V=n-depth[x];
    if(V&1){
        ups(fi=prf[x],g);
        ok[x]=(f[fi]<=V-1-Size[fi]) | 48;//换根
    }
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(fa[y]!=x) continue;
        ups(fi=g,y==prf[x] ? sef[x] : prf[x]);
        dfs2(y,fi);
    }
}

int main(){
    rei T; scanf("%d",&T);
    while(T--){
        tot=0; memset(head,0,sizeof head);
        scanf("%d",&n);
        for(rei i=1;i<n;++i){rei u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u);}
        if(dfs(1),only_root){putchar( (!f[1])|48 ),putchar(10); continue;}
        memset(ok,48,sizeof ok), ok[n+1]=0;
        dfs2(1),puts(ok+1);
    }
    getchar(); getchar();
    return 0;
}