CSS选择器 正则表达式 java 线程池 validation pyqt devise nuget rss spark项目 oracle可视化工具 matlab不等于怎么表示 java解析pdf python学习教程 java文件写入 java中random java文件输入输出 java格式化日期 java集合类型 python 教程 matlab2016a安装教程 bash命令 反转颜色 js获取父节点 网络文件服务器 滑动门代码 java获取时间戳 文章查重软件 js切割字符串 网红照片男 密码翻译 欧洲卡车模拟2存档 excel后缀 js对象转字符串 视频抠图 淘宝退货怎么上门取件 人马上单天赋 求字符串长度的函数 欧米伽小队提莫 wps脚注 cad合并成块
当前位置: 首页 > 学习教程  > 编程语言

Problem - K Russian Dolls on the Christmas Tree - Codeforces (树上启发式合并)

2020/11/24 10:35:50 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

Problem - K Russian Dolls on the Christmas Tree - Codeforces 题意 有一棵 nnn 个节点的树,节点编号为 1−n1-n1−n,111 号节点是根。问以每个节点为根的子树中,有多少个连续区间。 解法 子树?离线?立即推&…

Problem - K Russian Dolls on the Christmas Tree - Codeforces

题意

有一棵 n n n 个节点的树,节点编号为 1 − n 1-n 1n 1 1 1 号节点是根。问以每个节点为根的子树中,有多少个连续区间。

解法

子树?离线?立即推:树上启发式合并!

  • 统计子树每个编号的点出现的次数,同时维护答案;
  • 如果编号为 u u u 的点从无到有,就看编号为 u − 1 u-1 u1 u + 1 u+1 u+1 的点的出现情况,如果都出现了,就说明两个区间合并为一个,区间数减一,如果都没有出现,则新增一个区间。
  • 如果编号为 u u u 的点从有到无,就看编号为 u − 1 u-1 u1 u + 1 u+1 u+1 的点的出现情况,如果都出现了,就说明一个区间分裂成两个,区间数加一,如果都没有出现,则区间数减一。

解法

#pragma region
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
#define tr t[root]
#define lson t[root << 1]
#define rson t[root << 1 | 1]
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
#pragma endregion
const int maxn = 2e5 + 5;
int n;
vector<int> g[maxn];
int son[maxn], sz[maxn];
int res[maxn], flag;
int cnt[maxn], ans;
void init() {
    rep(i, 1, n) g[i].clear(), son[i] = 0;
}
void dfs1(int u, int f) {
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void count(int u, int f, int val) {
    cnt[u] += val;
    if (cnt[u - 1] && cnt[u + 1]) ans -= val;
    if (!cnt[u - 1] && !cnt[u + 1]) ans += val;
    for (auto v : g[u]) {
        if (v == f || v == flag) continue;
        count(v, u, val);
    }
}
void dfs(int u, int f, bool keep) {
    for (auto v : g[u]) {
        if (v == f || v == son[u]) continue;
        dfs(v, u, 0);
    }
    if (son[u]) {
        dfs(son[u], u, 1);
        flag = son[u];
    }
    count(u, f, 1);
    res[u] = ans;
    flag = 0;
    if (!keep) count(u, f, -1);
}
int main() {
    int T;
    scanf("%d", &T);
    rep(cas, 1, T) {
        scanf("%d", &n);
        init();
        rep(i, 1, n - 1) {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs1(1, 0);
        dfs(1, 0, 0);
        printf("Case #%d:", cas);
        rep(i, 1, n) printf(" %d", res[i]);
        puts("");
    }
}

本文链接: http://www.dtmao.cc/news_show_400285.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?