[HDU2196]Computer

二次扫描与换根法

这种算法通常用于统计无根树上每个结点的答案,并且对于根结点的答案容易统计的题目。这时,我们就把每个结点在 DFS 遍历的同时换作根,同时统计答案。

我们对整棵树做 2 次 dfs:

第一次:

选定一个结点为根(比如 1 号),计算 ,表示在 内离 最远的结点的距离,复杂度 .

这时, 即为距离 结点最远的结点的距离,满足题意。

第二次:

因为根结点的 为原问题的解,想到对于每一个结点 ,将其换作根,并修改一些 的值,使得 的值变成为以 为根时,在 内离 最远的结点的距离,这时, 即为对于结点 的原问题的解。

具体而言,假设当前的根为 ,对于 的所有子结点

  • 如果 的答案未被统计过(即 未被当作过根),就考虑把根换作
  • 这时,我们只用修改 的值(其他的结点的子树结构没有被改变)
  • 对于 ,它将失去一颗子树 ,因此为了保证 表示在 内离 最远的结点的距离,我们用 的其他子结点 重新计算 .
  • 那么对于 ,它将增加一颗子树 ,则用刚刚计算出的 更新 即可.
  • 优化一下,对于 所有需要换根的子结点 ,只需记录 的最大值和次大值。在对最大值对应的子结点换根时,使用次大值计算 ;在对除最大值之外的子结点换根时,使用最大值计算 。则换根的均摊复杂度 ,总复杂度 .

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10004;

int n;
struct qxx{int nex,t,v;};
qxx e[N*2];
int h[N],cnt,f[N],ans[N];
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}

bool vis[N];
int dfs1(int u){// 第一次扫描
    vis[u]=1;
    for(int i=h[u];i;i=e[i].nex)
        if(!vis[e[i].t])f[u]=max(f[u],dfs1(e[i].t)+e[i].v);
    return f[u];
}
void  dfs2(int u){vis[u]=1;
    ans[u]=f[u];
    int mx1=0,mx2=0,v1,ofu,ofv;// 用于回溯
    for(int i=h[u];i;i=e[i].nex){// 统计最大和次大
        if(f[e[i].t]+e[i].v>=mx1)mx2=mx1,mx1=f[e[i].t]+e[i].v,v1=e[i].t;
        else if(f[e[i].t]+e[i].v>mx2)mx2=f[e[i].t]+e[i].v;
    }
    for(int i=h[u];i;i=e[i].nex){const int& v=e[i].t,& w=e[i].v;
        if(!vis[v]){ofu=f[u],ofv=f[v],f[u]=0;
            if(v==v1)f[u]=mx2;// 如果要换的是最大值的子结点,就赋值为次大
            else f[u]=mx1;// 否则为最大值的子结点
            f[v]=max(f[v],f[u]+w);// 更新 f[v]
            dfs2(v);
            f[u]=ofu,f[v]=ofv;// 回溯
        }
    }
}
int main(){while(~scanf("%d",&n)){memset(e,0,sizeof(e));
        memset(h,0,sizeof(h));
        memset(f,0,sizeof(f));
        cnt=0;
        for(int i=2;i<=n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add_path(i,x,y);
            add_path(x,i,y);
        }
        memset(vis,0,sizeof(vis));
        dfs1(1);
        memset(vis,0,sizeof(vis));
        dfs2(1);
        for(int i=1;i<=n;i++){printf("%d\n",ans[i]);
        }
    }
    return 0;
}

  转载请注明: Sshwy's Blog [HDU2196]Computer

 上一篇
数位动态规划 数位动态规划
概述数位 DP 的基本思想就是按位 DP,对数字的每一位做 DP。 数位 DP 常用于求解区间内满足条件的数的计数问题。 数位 DP 的一个重要特征是多维度。事实上由于在数位 DP 的过程中有若干限制条件,使得问题的维度较多,因此相比普通
2018.11.16
下一篇 
[LuoguP1273] 有线电视网 [LuoguP1273] 有线电视网
题解树上背包。定义 表示在 中选 个用户的最大利润(可能为负)。目标即满足 的最大的 . 对于结点 ,将其子结点作为分组,做分组 01 背包。令
2018.11.08
  目录