题目描述
给你一棵n个点的树，每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是：把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来，求：有多少种方案可以使每种颜色交集产生的树非空。对k∈[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
题目链接：传送门
题解：不难发现，我们有一个优秀的N2N^2的dpdp做法，记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个，当前根选没选。
我们要知道分治NTTNTT的复杂度：对于kk个总度数∑deg=k\sum deg=k的多项式来说，计算它们乘积的复杂度可以做到：O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。
因此，我们采用重链剖分，先转移所有轻链。
不难发现，
g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))
【题目描述】风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。 由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，权值为c_i。接下来依次会有Q个水果掉下来，每个水果本质上也是一条
题目描述给定一棵n个点的树，点带点权。 有m次操作，每次操作给定x,y，表示修改点x的权值为y。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 输入输出格式输入格式： 第一行，n,m，分别代表点数和操作数。 第二行，V1,V2,...,Vn，代表nn个点的权值。 接下来n−1行，x,y，描述这棵树的n−1条边。 接下来m行，x,y，修改点x的权值为y。 输出格式： 对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。 保证答案在int范围内 输入输出样例输入样例#1： 复制10 10
-11 80
小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。 这个游戏的地图可以看作一棵包含 个结点和 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 到 的连续正整数。 现在有 个玩家，第 个玩家的起点为 ，终点为 。每天打卡任务开始时，所有玩家在第 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最
题目描述松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。 松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，......，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。 维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。 因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准
Description 一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身 Input 输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有 一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整
题目描述给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白 有两种操作： 0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑） 1 v : 询问1到v的路径上的第一个黑点，若无，输出-1 输入输出格式输入格式： 第一行 N，Q，表示N个点和Q个操作 第二行到第N行N-1条无向边 再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N). 输出格式： 对每个1 v操作输出结果 输入输出样例输入样例#1： 复制9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
题目背景数据规模和spoj上有所不同题目描述给定一棵n个节点的树，有两个操作： CHANGE i ti 把第i条边的边权变成ti QUERY a b 输出从a到b的路径中最大的边权，当a=b的时候，输出0输入输出格式输入格式： 第一行输入一个n，表示节点个数 第二行到第n行每行输入三个数，ui，vi，wi，分别表示 ui，vi有一条边，边权是wi 第n+1行开始，一共有不定数量行，每一行分别有以下三种可能 CHANGE，QUERY同题意所述 DONE表示输入结束 输出格式： 对于每个QUERY操作，输出一个数，表示a b之间边权最大值 输
题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和 输入输出格式输入格式： 第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含N个非负整数，分别依次
Rockdu's Blog