专栏首页ACM小冰成长之路51Nod-1803-森林直径

51Nod-1803-森林直径

ACM模版

描述

题解

根据题目,我们知道,数据是随机建树的,所以树的深度不会特别大,约摸 lg nlg\ n,所以我们可以树归搞搞,亲测,数据随机建树深度最大不超过 6161,大一点没毛病,小一点就 WAWA,至于官方题解中所说的解法,不是特别会写,只给大家贴一下参考参考。

官方题解:

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 5;
const int MAXM = 61;
const int MAXT = 5555;

int n, q, cnt;
int tmp, ans;
int fat[MAXT];
int pre[MAXT];
int hed[MAXN];
int Hed[MAXN];
int nxt[MAXN];
int Nxt[MAXT];
int dep[MAXN];
int Dep[MAXN];
int dp[MAXN][MAXM];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

void dfs(int x)
{
    Hed[x] = 0;
    for (int i = hed[x]; i; i = nxt[i])
    {
        dfs(i);

        if (i == hed[x])
        {
            Hed[x] = pre[cnt--];
            Nxt[Hed[x]] = Hed[i];
            Dep[Hed[x]] = dep[i];
            fat[Hed[x]] = i;
            for (int j = Hed[x]; j; j = Nxt[j])
            {
                dp[i][Dep[j] - dep[x]] = min(dp[i][Dep[j] - dep[x]], fat[j]);
            }
        }
        else
        {
            int t = pre[cnt--];
            Nxt[t] = Hed[i];
            Dep[t] = dep[i];
            fat[t] = i;
            Hed[i] = t;
            for (int j = Hed[i]; j; j = Nxt[j])
            {
                dp[i][Dep[j] - dep[x]] = min(dp[i][Dep[j] - dep[x]], fat[j]);
            }
            for (int j = Hed[x]; j; j = Nxt[j])
            {
                for (int k = Hed[i]; k; k = Nxt[k])
                {
                    dp[i][Dep[j] + Dep[k] - 2 * dep[x]] =
                        min(dp[i][Dep[j]+ Dep[k] - 2 * dep[x]], max(fat[j], fat[k]));
                }
            }
            for (int j = Hed[x], k = Hed[i]; k; k = Nxt[k], j = Nxt[j])
            {
                fat[j] = min(fat[j], fat[k]);
                if (!Nxt[j] && Nxt[k])
                {
                    Nxt[j] = Nxt[k];
                    break;
                }
            }
            for (int j = Hed[x], k = Hed[i]; k && j != k; j = Nxt[j], k = Nxt[k])
            {
                pre[++cnt] = k;
            }
        }
    }
}

void init()
{
    cnt = MAXT - 1;
    memset(dp, 0x3f, sizeof(dp));

    for (int i = 1; i < MAXT; i++)
    {
        pre[i] = i;
    }

}

int main()
{
    init();

    scan_d(n);

    int x, y;
    for (int i = 2; i <= n; i++)
    {
        scan_d(x);
        scan_d(y);
        nxt[i] = hed[x];
        hed[x] = i;
        dep[i] = dep[x] + 1;
    }

    dfs(1);

    for (int i = n - 1; i > 1; i--)
    {
        for (int j = 1; j < MAXM; j++)
        {
            dp[i][j] = min(dp[i][j], dp[i + 1][j]);
        }
    }

    scan_d(q);

    int l, r;
    while (q--)
    {
        scan_d(l);
        scan_d(r);
        l++;
        r++;
        tmp = 0;
        for (int i = 1; i < MAXM; i++)
        {
            if (dp[l][i] <= r)
            {
                tmp = i;
            }
            else
            {
                break;
            }
        }

        ans += tmp;
    }

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

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-5985-Lucky Coins

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <cstri...

    f_zyj
  • POJ-1961-Period

    ACM模版 描述 ? 题解 类似于 POJ-2406-Power Strings,不过这个题是要求处理所有的前缀的循环节,并且只输出循环节出现次数大于1 的前缀...

    f_zyj
  • 51Nod-1203-JZPLCM

    ACM模版 描述 ? 题解 这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。 首先将数进行拆解,拆...

    f_zyj
  • 【ZOJ2278】Fight for Food(dp)

    给定一个10*10以内的地图,和p(P<=30000)只老鼠,给定其出现位置和时间T(T<=1,000,000,000),求最多抓到几只老鼠。

    饶文津
  • Android实现状态栏(statusbar)渐变效果的示例

    1.用全屏模式或者状态栏透明的方式去实现,感觉很勉强 2.为了一个statusbar的效果,然后去处理一大堆不适应,我认为是不值得的.特别是软键盘弹出的问题 ...

    砸漏
  • 不相交集类应用:迷宫生成

    1 #include <iostream> 2 #include <vector> 3 #include <cstdlib> 4 #includ...

    用户1154259
  • LeetCode - 增减字符串匹配

    原题地址:https://leetcode-cn.com/problems/di-string-match/

    晓痴
  • 1077: 输入入门(2)

    描述:计算A+B 输入:输入第1行为一个整数n(1≤n≤10),代表测试的组数。下面有n组测试数据,每组1行,为2个整数,为A, B。 输出:输出A+B的值...

    bboysoul
  • 洛谷P4723 【模板】线性递推(多项式取模 线性代数)

    attack
  • loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)

    考虑K比较小的情况,可以直接暴力建SAM, 枚举w的子串算出现次数。询问用个 的vector记录一下每次在vector里二分就好。

    attack

扫码关注云+社区

领取腾讯云代金券