牛客国庆集训派对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)


相关推荐

  • django和drf_类中的方法可以序列化么

    django和drf_类中的方法可以序列化么前言上一篇文章我们讲述了序列化,这篇就带大家一起来实现以下序列化Serializer我们使用序列化类Serializer,我们来看下源码结构,这里推荐使用pycharm左边导航栏的Structu

  • UE4/UE5 使用Unreal Datasmith完全教程

    UE4/UE5 使用Unreal Datasmith完全教程(2019.12.9)Datasmith功能已内置到虚幻4.24版本Datasmith支持导入Twinmotion:Twinmotion教程汇总(2021.4.2)Datasmith安装到4.20-4.23版本:UE4在4.20-23版本安装Datasmith插件(2021.3.30更新)Datasmith导出插件:Datasmith导出插件(2021.4.12更新)导入sketchup草图大师:草图大师SU导入Unity和虚幻UE4对比导入Revit2018.3+:UE4使用Da.

  • Uefi安装Centos7出现错误以及解决方法

    Uefi安装Centos7出现错误以及解决方法写这篇就当是学习的笔记和总结。文笔不好有什么错别字或不通的地方大家多担待。很少使用Linux系统,前段时间因工作需要,要在一台服务器上安装centos7,服务器默认的引导方式是Uefi,下载ISO镜像用UltraISO刻U盘后引导安装但是报错,进后dracut#命令行,当时完全是懵的一堆英文单字没几个认识。只能百度搜索出错原因和解决方法,以下就是网上说的方法和自己实践的总结。…

  • python编程控制示波器设备_基于Python的示波器的截屏GUI界面[通俗易懂]

    python编程控制示波器设备_基于Python的示波器的截屏GUI界面[通俗易懂]importtimeimporttkinterastkfromtkinterimport*fromtkinterimportttkclassScreenCapture(object):def__init__(self):self.idn=self.__class__.__name__#InstrumentInitialisation#self.instr=MyIn…

    2022年10月12日
  • linux搭建svn服务器客户端_搭建web服务器的步骤

    linux搭建svn服务器客户端_搭建web服务器的步骤Linux搭建SVN服务器

  • 口罩、安全帽识别比赛踩坑记(一) 经验漫谈及随想

    口罩、安全帽识别比赛踩坑记(一) 经验漫谈及随想前言       因为疫情迎来的史无前例大假期,从开始理直气壮的天天划手机,到中间百无聊赖的躺尸,再到之后实在憋得慌,就想找点什么事搞一搞。恰好这时,一直关注的极视角联合Intel公司举办了一个对口罩和安全帽进行识别的比赛,能免费用一个月的云服务器对于我这还在用跑个Demo都能卡死的老爷机来说还是相当具有吸引力的。于是…

发表回复

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

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