标签: 树型DP

「NowCode」杀树

牛牛学习了树。

给出一棵节点数为 n 的树,删去一个点 i 的代价为 aia_i,一条链的长度定义为路径上 点 的个数。一棵树死了,满足不存在一条长度 l\geq l 的链,牛牛希望用最少代价杀死这棵树。

「CodeForces 1220E」 Tourism

Alex decided to go on a touristic trip over the country.

For simplicity let's assume that the country has 𝑛 cities and 𝑚 bidirectional roads connecting them. Alex lives in city 𝑠 and initially located in it. To compare different cities Alex assigned each city a score 𝑤𝑖 which is as high as interesting city seems to Alex.

「CodeForces 1249E」Maximum Weight Subset

You are given a tree, which consists of 𝑛 vertices. Recall that a tree is a connected undirected graph without cycles.

Example of a tree.
Vertices are numbered from 1 to 𝑛. All vertices have weights, the weight of the vertex 𝑣 is 𝑎𝑣.

Recall that the distance between two vertices in the tree is the number of edges on a simple path between them.

「LOJ10157」 皇宫守卫

太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。

皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状,某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。

「ZJOI2008」 骑士

Z国的骑士团是一个很有势力的组织,帮会中汇聚了来自各地的精英。他们劫富济贫,惩恶扬善,受到社会各界的赞扬。

最近发生了一件可怕的事情,邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里,在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上,就像期待有一个真龙天子的降生,带领正义打败邪恶。