题目大意： 给一棵树，每个节点有一个颜色。写一个程序支持把两个点路径上的所有点染成一个颜色，查询两点之间的色段数量。 解题思路： 树链剖分+线段树 首先它是一颗树，而且是修改和查询两点路径上的颜色，可以想到树链剖分。 查询颜色段数可以用线段树维护区间颜色段数。 这道题涉及到区间合并，所以在线段树和lca的时候需要多记录一些东西，当前区间的最左边的颜色，最右边的颜色，已经求出的区间

题目大意： 给定一棵根节点为1的带边权的树。 每次给定一些点，求把这些点与树根断开的最小花费。 题目分析： 我们可以O（n）处理出每个点与根断开的最小花费，即该节点到根的路径上的最小边权。 然后我们对于每一个询问，可以把询问的点打上标记，然后可以O（n）动态规划求解。 但是O（n）的时间复杂度接受不了，而且我们发现每次询问并不会询问所有的点，而且询问的总点数不超过50w。 这样我们可

虚树入门 题目传送门 虚树的主要思想就是对于一棵树，仅仅保留有用的点，重新构建一棵树。 #include<bits/stdc++.h>#define il inline#define pb push_back#define ms(_data,v) memset(_data,v,sizeof(_data))#define SZ(a) int((a).size())using name

Description 在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望

怎么SDOI2011和SDOI2019的两道题这么像啊。。(虽然并不完全一样) 题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=2281 (luogu) https://www.luogu.org/problemnew/show/P2490 题解: 博弈论好难啊完全学不来QAQ 题目里应该有个限制，是先手不能左移，后手不

题意 求树上路径点颜色的块数，带修改操作。 思路 先把树剖成若干链，用线段树维护区间的块数。 查询统计答案时，当一条链调到另一条链，判断一下这两个端点是否相等（即为同一块）。两个点跳时都这样操作。 当两个点到了同一条链上，需要两个端点都和它们上一次查询到的端点判断（因为在循环中去掉的是上一次和现在的重复，此处是循环结束后特判）。 细节详见代码。 代码 #include <cstdi

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=2286 题目大意 给定一棵树，树上有边权，切断一条边消耗边权大小的能量 每次给定一些关键点，使这些关键点都不能与1联通，询问最小代价 题解 树形DP dp[i]:使i不与它子树中任意一个关键点联通的最小代价 dp[i]:使i不与它子树中任意一个关键点联通的最小代价 dp[i

2243: [SDOI2011]染色 Time Limit: 20 Sec Memory Limit: 512 MB Description 给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。 请你写一个

Description 给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。 请你写一个程序依次完成这m个操作。 Input 第一行包含2个整数n和m，分别表示节点数和操作数； 第二行包含n个正整数表示n个节点的初始颜

title : [SDOI2011]染色（路径染色+色段查询） tags : ACM,数据结构 date : 2021-11-16 author : Linno P2486 [SDOI2011]染色 题面 给一棵树，支持两种操作： ①给定u,v,w，将u到v的路径上所有节点染成颜色w。 ②给定u,v，查询u到v路径上颜色段的数量。 树链剖分+线段树 树链剖分将无根树拍平后，用