A-啊啊啊啊啊_一起来做题~欢乐赛7

题目描述

样例

算法1

(换根dp)

分析：

大体的思路就是先以某个节点为根计算出一个权值
接着从这个节点开始移动
计算每次从当前节点u移动到其子节点v对答案的影响
影响就是减去以子节点v为根的子树所有节点经过边<u,v>的距离
加上除v为根节点的子树外的所有节点经过边<u,v>的距离

状态转移：

状态表示： $f[u]$ 为以u为根的子树的权值

树形dp部分：

$f[u] = \sum f[v] + sz[v]$

解释： $sz[v]$ 为以v为根的子树大小，每个节点经过边<u,v>都有一个贡献
换根dp部分：

$f[v] = f[u] - sz[v] + (n - sz[v])$

解释：- sz[v]先将以v为根的子树的影响消除，+ (n - sz[v]) 增加除以v为根的子树的节点外的点经过边<u,v>的贡献

细节：

每一条边的贡献不是单纯的1而是经过这条边的节点个数，可以说是子树大小

时间复杂度 $O(n)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 1000010;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
int h[N],ne[N * 2],e[N * 2],idx;
LL f[N];
int sz[N];
LL ans;
int n;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs1(int u,int father)
{
    sz[u] = 1;
    f[u] = 0;
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs1(j,u);
        f[u] += f[j] + sz[j];
        sz[u] += sz[j];
    }
}

void dfs2(int u,int father)
{
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        f[j] = f[u] - sz[j] + (n - sz[j]);
        dfs2(j,u);
    }
    ans = min(ans,f[j]);
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) h[i] = -1;
    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    ans = f[1];
    dfs2(1,0);
    printf("%lld\n",ans);
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}