P1364题解

· · 个人记录

可以利用动态思想，首先生成一个候选答案，然后根据候选答案节点的移动，考虑答案整体的变化。

我们的工作分为如下几步：

1.读入和预处理

我们可以在读入的过程中，记录每个节点的深度，并且保证1号节点的深度为0——虽然题目中没有明确说明，但是数据其实保证了1号节点是根节点——这样我们容易得到初始解ans。

之后我们做一个简单的预处理，得到数组sum[]，sum[u]的含义是以u为根的子树的子树和。

2.计算

前言中提到，我们的思路是在一个初始答案上移动候选点以得到新的答案，当我们遍历n个节点后，最优的答案即为所求。

对于上图，假定我们已经获得了以e为候选点的候选答案，正准备移动到c点获得新的答案，我们容易发现：

  1. 以e为根的子树中的所有节点距离候选点的距离都增加了1
  2. 除去子树e的其他部分的所有节点距离候选点的距离都减少了1

于是我们得到等式 ans[c]=ans[e]+sum[e]-(tot-sum[e])

而同理，当我们从c向e移动时，即有等式 ans[e]=ans[c]-sum[e]+(tot-sum[e])

分析上述过程，算得初始答案ans的过程是O(n)的，移动并更新答案是O(1)的，共进行O(n)次，即计算过程是O(n)的，整体的时间复杂度即为O(n)。

而经过分析，我们可以从1号节点开始，向下通过搜索的方式进行遍历，即可不必考虑上述的第二种情况，得到代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=100+10;
int n;
int dep[maxn];
int val[maxn],sum[maxn];
vector<int> G[maxn];
int ans,tot;

void read(){
    cin>>n;
    dep[1]=0;
    for(int i=1;i<=n;++i){
        int l,r;
        scanf("%d%d%d",val+i,&l,&r);
        if(l) G[i].push_back(l),dep[l]=dep[i]+1;
        if(r) G[i].push_back(r),dep[r]=dep[i]+1;
        ans+=val[i]*dep[i];
        tot+=val[i];
    }
}

int dp(int u){
    if(G[u].empty()) return sum[u]=val[u];
    int res=0;
    for(int i=0;i<G[u].size();++i) res+=dp(G[u][i]);
    return sum[u]=res+val[u];
}

void prework(){
    dp(1);
}

void dfs(int u,int v,int res){
    res+=tot-sum[v];
    res-=sum[v];
    ans=min(ans,res);
    for(int i=0;i<G[v].size();++i) if(G[v][i]!=u) dfs(v,G[v][i],res);
}

void solve(){
    for(int i=0;i<G[1].size();++i) dfs(1,G[1][i],ans);
    cout<<ans<<endl;
}

int main(){
    read();
    prework();
    solve();
    return 0;
}