牛客国庆集训派对Day6 I.清明梦超能力者黄YY(树剖)「建议收藏」

牛客国庆集训派对Day6 I.清明梦超能力者黄YY(树剖)「建议收藏」题目:https://www.nowcoder.com/acm/contest/206/I正难则反。问你倒数第k次的颜色,正着来搞不定,那就转换成“倒着来的第k次”。使用树剖将这棵树丢进线段树里,不维护染色,而是维护更新的次数(因为除了倒数第k次的颜色,其他的根本没用啊!!!),然后把区间最小值pushUp到树顶。更新完染色次数之后,用树顶来判整个区间里是否存在已经被更新了k次的节点,如果…

大家好,又见面了,我是你们的朋友全栈君。

题目:https://www.nowcoder.com/acm/contest/206/I
正难则反。
问你倒数第k次的颜色,正着来搞不定,那就转换成“倒着来的第k次”。
使用树剖将这棵树丢进线段树里,不维护染色,而是维护更新的次数(因为除了倒数第k次的颜色,其他的根本没用啊!!!),然后把区间最小值pushUp到树顶。
更新完染色次数之后,用树顶来判整个区间里是否存在已经被更新了k次的节点,如果存在,就一步步往下走去找到那个节点。由于节点不止一个,进树之后两边都要检查能否往下走。
这和我之前做的:南京网络赛里的一题是同一种操作,可以点进去查看。

赠送祖传样例:

9 5 2
1 2
2 3
1 4
4 5
4 6
6 8
6 7
8 9
1 6 3
4 9 1
5 7 4
3 6 2
2 8 3

答案:2 2 0 2 0 2 0 1 0

ac代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int inf = 1e9 + 7;
vector<int> G[maxn];
int n, m, k;
int sz[maxn], dep[maxn];
int ch[maxn], fa[maxn];
int top[maxn], tid[maxn], tid2[maxn];
int ans[maxn];
int tot;
void dfs1(int u, int f, int d) { 

sz[u] = 1;
fa[u] = f;
dep[u] = d;
for(int i = 0; i < G[u].size(); i++) { 

int v = G[u][i];
if(v == f) { 

continue;
}
dfs1(v, u, d + 1);
sz[u] += sz[v];
if(ch[u] == -1 || sz[v] > sz[ch[u]]) { 

ch[u] = v;
}
}
}
void dfs2(int u, int tp) { 

top[u] = tp;
tid[u] = ++tot;
tid2[tot] = u;
if(ch[u] == -1) { 

return;
}
dfs2(ch[u], tp);
for(int i = 0; i < G[u].size(); i++) { 

int v = G[u][i];
if(v != ch[u] && v != fa[u]) { 

dfs2(v, v);
}
}
}
struct SegmentTree { 

int t[maxn << 2], lazy[maxn << 2];
void pushUp(int i) { 

t[i] = min(t[i << 1], t[i << 1 | 1]);
}
void pushDown(int i) { 

if(!lazy[i]) { 

return;
}
t[i << 1] -= lazy[i];
t[i << 1 | 1] -= lazy[i];
lazy[i << 1] += lazy[i];
lazy[i << 1 | 1] += lazy[i];
lazy[i] = 0;
}
void build(int i, int l, int r) { 

lazy[i] = 0;
if(l == r) { 

t[i] = k;
return;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
pushUp(i);
}
void update(int i, int l, int r, int L, int R) { 

if(l >= L && r <= R) { 

t[i] -= 1;
lazy[i] += 1;
return;
}
pushDown(i);
int mid = (l + r) >> 1;
if(L <= mid) { 

update(i << 1, l, mid, L, R);
}
if(R > mid) { 

update(i << 1 | 1, mid + 1, r, L, R);
}
pushUp(i);
}
void update_cor(int i, int l, int r, int cor) { 

if(l == r && !t[i]) { 

t[i] = inf;
ans[tid2[l]] = cor;
return;
}
pushDown(i);
int mid = (l + r) >> 1;
if(!t[i << 1]) { 

update_cor(i << 1, l, mid, cor);
}
if(!t[i << 1 | 1]) { 

update_cor(i << 1 | 1, mid + 1, r, cor);
}
pushUp(i);
}
void update(int u, int v, int c) { 

int f1 = top[u], f2 = top[v];
while(f1 != f2) { 

if(dep[f1] < dep[f2]) { 

swap(f1, f2);
swap(u, v);
}
update(1, 1, n, tid[f1], tid[u]);
u = fa[f1];
f1 = top[u];
}
if(dep[u] < dep[v]) { 

swap(u, v);
}
update(1, 1, n, tid[v], tid[u]);
if(!t[1]) { 

update_cor(1, 1, n, c);
}
}
} st;
struct Query { 

int u, v, c;
} q[maxn];
int main() { 

scanf("%d%d%d", &n, &m, &k);
tot = 0;
memset(ch, -1, sizeof(ch));
int u, v;
for(int i = 1; i <= n - 1; i++) { 

scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1, 0, 0);
dfs2(1, 1);
st.build(1, 1, n);
for(int i = 1; i <= m; i++) { 

scanf("%d%d%d", &q[i].u, &q[i].v, &q[i].c);
}
for(int i = m; i >= 1; i--) { 

st.update(q[i].u, q[i].v, q[i].c);
}
for(int i = 1; i <= n; i++) { 

printf("%d", ans[i]);
if(i < n) { 

printf(" ");
}
}
printf("\n");
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159270.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • fbx转3dtiles

    fbx转3dtilesfbx转3dtiles

    2022年10月27日
  • pycharm编制索引_网页制作作品源代码

    pycharm编制索引_网页制作作品源代码tree/f/a>codeTree.txt

  • 史上最好听的十首纯音乐推荐[通俗易懂]

    史上最好听的十首纯音乐推荐[通俗易懂]天然去雕饰,清水出芙蓉。不需要歌词我们就能感受到那或美丽忧伤,或轻灵欢快,或激昂艰辛的情绪。思绪随着旋律而起伏,心中莫名就有一种感动,无法用词语表达,无言却胜过万语千言。一、《LuvLetter》

  • IntelliJ IDEA使用教程(新手入门–持续更新)[通俗易懂]

    IntelliJ IDEA使用教程(新手入门–持续更新)[通俗易懂]idea使用教程一、下载安装二、基础配置及插件安装1.基础配置1.1配置jdk1.2配置maven1.3配置git1.4开启自动编译1.5调整字体(参照配置入口,大家可以根据喜好自行调整,记得调整完每一步都要点击apply)1.6取消大小写敏感,取消勾选1.7设置统一编码为utf-82、插件下载2.1[Mybatis](https://how2j.cn/k/mybatis/mybatis-tutorial/1087.html)2.2[Lombok](https://www.zhihu.com/q

  • 积分中值定理_三个中值定理的公式

    积分中值定理_三个中值定理的公式设$f:[a,b]\to\mathbf{R}$是区间$[a,b]$上的连续函数,其中$a,b\in\mathbf{R}$且$a<b$.则存在$a<\varepsilon<b$,使得

  • matlabGUI入门

    matlabGUI入门1基础知识1.1函数1.2数据类型1.3绘图1.4其它2GUIDE2.1创建GUI界面2.2模板选择2.3控件2.4对象浏览器2.5回调函数2.6属性检查器2.7数据传输由窗口、菜单、图标、光标、按键、对话框和文本等各种图形对象组成的用户界面叫作图形用户界面(GUI)。它可以允许用户定制与MATLAB的交互方式,从而命令窗口不再是唯一与MATLAB的交互方式。用户通过鼠标或键盘选择、激活这些图形对象,使计算机产生某种动作或变化。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号