题目链接

题意

定义\(L(a,b)\)为结点\(a\)到结点\(b\)的路径上的结点数，问有种\(pair(L(a,b),L(c,d))\)取值，其中结点\(a\)到结点\(b\)的路径与结点\(c\)到结点\(d\)的路径没有交叉。

思路

我们很容易想到要想两条路径不交叉，那么\(a,b\)与\(c,d\)必定在两棵不同的子树中，假设第一棵子树的直径位\(L1\)，第二棵子树的直径为\(L2\)，那么我们可以得知\([1,L1]\)必定可以与\([1,L2]\)进行匹配，那么对于\([1,L1]\)中的每个数\(x\)可以和\([1,L2]\)中的每个数\(y\)构成满足题意的\(pair(x,y)\)，此时\(x\)的贡献就是\(L 2\)，由于不能重复，因此我们对每个长度可以匹配的方案取一个\(max\)，最后加起来就是答案了。

最后本题的难点就变成了求断开每条链后产生的两棵子树的直径了。

我们定义\(dp[i][0]\)为以\(i\)为根节点的子树中以\(i\)为一个端点的最长距离，\(dp[i][1]\)为次远，\(dp[i][2]\)为第\(3\)远，那么这个子树的直径为\(max(\)以\(i\)为子树中不经过\(i\)的最长链，经过\(i\)的最长链\()\)，\(dp[i][3]\)为\(i\)从其父亲结点往父亲的其他链能到达的最远距离，则断开\(i\)与其父亲的这条链生成的另一棵子树的直径就为\(max(\)不经过\(i\)的父亲结点的最长链，经过\(i\)的父亲结点的最长链\()\)，具体转移请看代码。

代码

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson (rt<<1)

#define rson (rt<<1|1)

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)

#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;

const int mod = 1000000007;

const int maxn = 100000 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int t, n, tot;

int head[maxn], dept[maxn], u[maxn], v[maxn], w[maxn];

int dp[maxn][5], L1[maxn], L2[maxn], ans[maxn], len[maxn][3];

struct edge {

    int v, w, next;

}ed[maxn*2];

void add(int u, int v, int w) {

    ed[tot].v = v;

    ed[tot].w = w;

    ed[tot].next = head[u];

    head[u] = tot++;

}

void dfs1(int u, int p, int d) {

    dept[u] = d;

    for(int i = head[u]; ~i; i = ed[i].next) {

        int v = ed[i].v;

        if(v == p) continue;

        dfs1(v, u, d + 1);

        int tmp = dp[v][0] + ed[i].w;

        if(tmp > dp[u][0]) swap(tmp, dp[u][0]);

        if(tmp > dp[u][1]) swap(tmp, dp[u][1]);

        if(tmp > dp[u][2]) swap(tmp, dp[u][2]);

        L1[u] = max(L1[u], L1[v]);

    }

    L1[u] = max(L1[u], dp[u][0] + dp[u][1]);

}

void dfs2(int u, int p) {

    len[u][0] = len[u][1] = 0;

    for(int i = head[u]; ~i; i = ed[i].next) {

        int v = ed[i].v;

        if(v == p) continue;

        int tmp = L1[v];

        //处理不经过u的最长链

        if(tmp > len[u][0]) swap(tmp, len[u][0]);

        if(tmp > len[u][1]) swap(tmp, len[u][1]);

    }

    for(int i = head[u]; ~i; i = ed[i].next) {

        int v = ed[i].v;

        if(v == p) continue;

        //经过u的最长链

        if(dp[u][0] == dp[v][0] + ed[i].w) {

            dp[v][3] = max(dp[u][3], dp[u][1]) + ed[i].w;

            L2[v] = max(dp[u][3], dp[u][2]) + dp[u][1];

        } else {

            dp[v][3] = max(dp[u][3], dp[u][0]) + ed[i].w;

            if(dp[u][1] == dp[v][0] + ed[i].w) {

                L2[v] = max(dp[u][3], dp[u][2]) + dp[u][0];

            } else {

                L2[v] = max(dp[u][3], dp[u][1]) + dp[u][0];

            }

        }

        //处理掉不经过u的最长链是否是由以v这棵子树贡献的情况

        if(len[u][0] != L1[v]) L2[v] = max(L2[v], len[u][0]);

        else L2[v] = max(L2[v], len[u][1]);

        dfs2(v, u);

    }

}

int main() {

#ifndef ONLINE_JUDGE

    FIN;

#endif

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        tot = 0;

        for (int i = 1; i <= n; ++i) head[i] = -1, dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = L1[i] = L2[i] = dept[i] = ans[i] = 0;

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

            scanf("%d%d", &u[i], &v[i]);

            add(u[i], v[i], 1), add(v[i], u[i], 1);

        }

        dfs1(1, 0, 0);

        dfs2(1, 0);

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

            int x = u[i], y = v[i];

            if(dept[x] < dept[y]) swap(x, y);

            //由于我保存的直径是路径上的边数，因此结点数要为边数+1

            ans[L1[x] + 1] = max(ans[L1[x] + 1], L2[x] + 1);

            ans[L2[x] + 1] = max(ans[L2[x] + 1], L1[x] + 1);

        }

        LL sum = 0;

        for(int i = n; i >= 1; --i) {

            ans[i] = max(ans[i], ans[i+1]);

            sum += ans[i];

        }

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

    }

    return 0;

}

巴特西

Rikka with Travels(2019年杭电多校第九场07题+HDU6686+树形dp)

题目链接

题意

思路

代码

最新文章

热门文章