树dp...吧 ZOJ 3949

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5568

Edge to the Root

Time Limit: 1 Second Memory Limit: 131072 KB

Given a tree with n vertices, we want to add an edge between vertex 1 and vertex x, so that the sum of d(1, v) for all vertices v in the tree is minimized, where d(u, v) is the minimum number of edges needed to pass from vertex u to vertex v. Do you know which vertex x we should choose?

Recall that a tree is an undirected connected graph with n vertices and n - 1 edges.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1 ≤ n ≤ 2 × 10⁵), indicating the number of vertices in the tree.

Each of the following n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n), indicating that there is an edge between vertex u and v in the tree.

It is guaranteed that the given graph is a tree, and the sum of n over all test cases does not exceed 5 × 10⁵. As the stack space of the online judge system is not very large, the maximum depth of the input tree is limited to about 3 × 10⁴.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

Output

For each test case, output a single integer indicating the minimum sum of d(1, v) for all vertices v in the tree (NOT the vertex x you choose).

Sample Input

Sample Output

8

2

Hint

For the first test case, if we choose x = 3, we will have

d(1, 1) + d(1, 2) + d(1, 3) + d(1, 4) + d(1, 5) + d(1, 6) = 0 + 1 + 1 + 2 + 2 + 2 = 8

It's easy to prove that this is the smallest sum we can achieve.

Author: WENG, Caizhi
Source: The 17th Zhejiang University Programming Contest Sponsored by TuSimple

题目大意：给你一棵树，这棵树的每条边的length都是1。然后这棵树是以1为root，定义他的weight就是所有的节点的deep和。

现在你有一个操作，对于任意的u，可以从(1,u)连接一条边，问选择哪个节点u连接可以使得树的weight最小。

思路：其实很早就有思路了...但是最近心情太烦了，写的时候都很烦，就没有做。

刚开始sb的用线段树啊，树状数组啊来维护，发现好烦。然后第二天删光了所有的代码重新来，但还是摆脱不了树状数组...（感觉就算写对了应该也是TLE了）

今天突然发现可以维护一下前缀就好了（真的是......）

首先我们可以发现，对于(1,u)连接了边以后，那么深度为deep[u]/2 + 1的这些点的deep都会发生改变。

我们从1开始进行dfs，然后我们对于经过的所有的节点，都把他定义为deep = 1.然后定义前面一个子树的区间为[l, r]，当前的区间为[L, R]，然后利用这个进行修改即可

具体的就是容斥一下就好了，还不懂看着代码里面的注释，然后自己画一画

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn = 2e5 + ;

int n;

vector<int> G[maxn];

int deep[maxn], sz[maxn];

LL cnt[maxn];

void dfs_sz(int u, int fa, int d){

    deep[u] = d; sz[u] = ; cnt[u] = d;

    for (int i = ; i < G[u].size(); i++){

        int v = G[u][i];

        if (v == fa) continue;

        dfs_sz(v, u, d + );

        sz[u] += sz[v];

        cnt[u] += cnt[v];

    }

}

LL ans;

LL rest, res, addval;

///rest表示每次需要加回来的东西是多少，addval表示rest的和

///res表示把路上经过的点deep都变成1所剩下的val

LL pre[maxn];//表示深度为l的有多少节点是被修改了的

void dfs_solve(int u, int fa, int l, int r){

    pre[deep[u]] = sz[u];

    int L = deep[u] /  + , R = deep[u];

    if (R > r) res -= sz[u] * (deep[u] - );///减去子树的

    if (L > l) rest -= pre[l];///减去之前子树的size

    addval += rest;

    ans = min(ans, addval + res);

    for (int i = ; i < G[u].size(); i++){

        int v = G[u][i];

        if (v == fa) continue;

        pre[deep[u]] -= sz[v];

        rest += pre[deep[u]];

        res += (deep[u] - ) * sz[v];

        dfs_solve(v, u, L, R);

        res -= (deep[u] - ) * sz[v];

        rest -= pre[deep[u]];

        pre[deep[u]] += sz[v];

    }

    if (R > r) res += sz[u] * (deep[u] - );

    addval -= rest;

    if (L > l) rest += pre[l];

}

int main(){

    int t; cin >> t;

    while (t--){

        scanf("%d", &n);

        for (int i = ; i <= n; i++) G[i].clear();

        for (int i = ; i < n; i++){

            int u, v; scanf("%d%d", &u, &v);

            G[u].pb(v), G[v].pb(u);

        }

        dfs_sz(, , );

        res = ans = cnt[];

        addval = ;

        for (int i = ; i < G[].size(); i++){

            int v = G[][i];

            dfs_solve(v, , , );

        }

        printf("%lld\n", ans);

    }

    return ;

}

/*

456

7

1 2

2 3

3 4

3 5

5 7

4 6

ans = 12

*/

巴特西