练习赛99D二次扫描与换根

第一遍扫描只计算以该点为根的其子树部分的最优解

第二遍扫描利用父节点的最优解计算以该点为根的子树部分加其余部分最优解

void dfs1(int u,int fa){
    int mx1 = 0,mx2 = 0;
    for(int i=head[u];~i;i=e[i].nxt){
        int v = e[i].v;
        if(v==fa) continue;
        dfs1(v,u);
        dp1[u]+=dp1[v]+tot[v]*u;
        mx1 = tot[v];
        dp1[u] += mx1*mx2*u;
        mx2 += mx1;
    }
}

void dfs2(int u,int fa){
    for(int i=head[u];~i;i=e[i].nxt){
        int v = e[i].v;
        if(v==fa) continue;
        dp2[v] = dp2[u]+tot[v]*(n-tot[v])*(v-u);
        dfs2(v,u);
    }
}

int dfs3(int u,int fa){
    int ans = 1;
    for(int i=head[u];~i;i=e[i].nxt){
        int v = e[i].v;
        if(v==fa) continue;
        ans += dfs3(v,u);
    }
    return tot[u]=ans;
}

void solve(){
    dfs3(1,0);
    dfs1(1,0);
    dp2[1] = dp1[1];
    dfs2(1,0);
    int mx = 0,p=-1;
    _rep(i,1,n){
        if(dp2[i]>mx){
            mx = dp2[i];
            p = i;
        }
    }
    int sum = 0;
    _rep(i,1,n) sum+=i;
    cout<<p<<" "<<2*mx+sum;
}