标签: 树上问题

「CF1263F」Economic Difficulties

An electrical grid in Berland palaces consists of 2 grids: main and reserve. Wires in palaces are made of expensive material, so selling some of them would be a good idea!

Each grid (main and reserve) has a head node (its number is 1). Every other node gets electricity from the head node. Each node can be reached from the head node by a unique path. Also, both grids have exactly n nodes, which do not spread electricity further.

「P2664」 树上游戏

lrb有一棵树,树的每个节点有个颜色。给一个长度为n的颜色序列,定义s(i,j)s(i,j)iijj 的颜色数量。以及

f(i)=i=1ns(i,j)f(i) = \sum_{i=1}^n s(i,j)

求出所有f(i)f(i)

「AtCoder 133F」Colorful Tree

There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex ai and Vertex bi, and the color and length of that edge are ci and di, respectively. Here the color of each edge is represented by an integer between 1 and N−1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

  • Query j (1≤j≤Q): assuming that the length of every edge whose color is xj is changed to yj, find the distance between Vertex uj and Vertex vj. (The changes of the lengths of edges do not affect the subsequent queries.)

「SCOI2015」情报传递

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 n 名情报员。每名情报员可能有若干名 (可能没有) 下线,除 1 名大头目外其余 n−1 名情报员有且仅有 1 名上线。奈特公司纪律森严,每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。

奈特公司每天会派发以下两种任务中的一个任务: