【Codeforces】CF 2007 E

E. Iris and the Tree

#树形结构 #贪心 #数学

题目描述

Given a rooted tree with the root at vertex $1$. For any vertex $i$ ($1\le i\le n$) in the tree, there is an edge connecting vertices $i$ and $p_i$ ($1\le p_i\le i$), with a weight equal to $t_i$.

Iris does not know the values of $t_i$, but she knows that $\sum _{i=2}^n{t}_i=w$ and each of the $t_i$ is a non-negative integer.

The vertices of the tree are numbered in a special way: the numbers of the vertices in each subtree are consecutive integers. In other words, the vertices of the tree are numbered in the order of a depth-first search.

The tree in this picture satisfies the condition. For example, in the subtree of vertex $2$, the vertex numbers are $2,3,4,5$, which are consecutive integers.

The tree in this picture does not satisfy the condition, as in the subtree of vertex $2$, the vertex numbers $2$ and $4$ are not consecutive integers.

We define $\mathrm{dist}(u,v)$ as the length of the simple path between vertices $u$ and $v$ in the tree.

Next, there will be $n-1$ events:

• Iris is given integers $x$ and $y$, indicating that $t_x=y$.

After each event, Iris wants to know the maximum possible value of $\mathrm{dist}(i,i\mathrm{mod}n+1)$ independently for each $i$ ($1\le i\le n$). She only needs to know the sum of these $n$ values. Please help Iris quickly get the answers.

Note that when calculating the maximum possible values of $\mathrm{dist}(i,i\mathrm{mod}n+1)$ and $\mathrm{dist}(j,j\mathrm{mod}n+1)$ for $i\ne j$, the unknown edge weights may be different.

输入格式

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $w$ ($2\le n\le 2\cdot 10^5$, $0\le w\le 10^{12}$) — the number of vertices in the tree and the sum of the edge weights.

The second line of each test case contains $n-1$ integers $p_2,p_3,\dots ,p_n$ ($1\le p_i\le i$) — the description of the edges of the tree.

Then follow $n-1$ lines indicating the events. Each line contains two integers $x$ and $y$ ($2\le x\le n$, $0\le y\le w$), indicating that $t_x=y$.

It is guaranteed that all $x$ in the events are distinct. It is also guaranteed that the sum of all $y$ equals $w$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

输出格式

For each test case, output one line containing $n-1$ integers, each representing the answer after each event.

样例 #1

样例输入 #1

4
2 1000000000000
1
2 1000000000000
4 9
1 1 1
2 2
4 4
3 3
6 100
1 2 3 2 1
6 17
3 32
2 4
4 26
5 21
10 511
1 2 2 4 2 1 1 8 8
3 2
6 16
10 256
9 128
2 1
5 8
8 64
4 4
7 32

样例输出 #1

2000000000000
25 18 18
449 302 247 200 200
4585 4473 2681 1567 1454 1322 1094 1022 1022

解法

解题思路

首先，我们有$n$条路径，一开始，当还没有路径被固定值的时候，我们的路径总和为$n\ast w$，也就是我们对每条路径都分配一个最大值，其他路径分配为$0$。

考虑但存在一条路径被固定时，会发生什么？

首先，这棵树是根据$dfs$序来构建的数，并且路径两点分别为$(i,i\%n+1)$，通过观察发现，设这条路径为为$u-v$，经过这条边的路径就两种：

$1.$ $u-v$这条边

$2.$ $v-maxso{n}_v$，其中$maxso{n}_v$指的是$v$子树的最大$dfs$序节点。

因此，我们在固定这条边路径大小时，也会使得这两条路径失去相应的大小，我们无法再指定它们为$w$了，而是指定其为$w-y$，这里$y$为指定的边权，那么我们总共减少$(n-2)\ast y$的权值。

同时，当一条路径上的所有边都被固定了值以后，这个路径也会失去$w-sum$的大小，其中$sum$是已经指定路径的全部大小。 原因很显然，因为这条路径所有的边都被固定了，它不应该是原来的$w$了，应该减去多出来的一部分，即$w-sum$

同时，我们还应该记录这样完全被固定边的路径,，记为$s$，在每一次指定新边的时候，由于可分配的路径数变为了$n-s$，我们相应的权值应该减少$(n-s-2)\ast y$

代码

void solve() {
int n, w;
std::cin >> n >> w;

std::vector<std::vector<int>>e(n + 1);
for (int i = 2; i <= n; ++i) {
int u;
std::cin >> u;
e[u].push_back(i);
}

std::vector<int>son(n + 1), deep(n + 1);
std::vector<std::array<int, 24>> fa(n + 1);
auto dfs = [&](auto&& self, int u, int Fa) ->void {
deep[u] = deep[Fa] + 1; son[u] = u;

fa[u][0] = Fa;
for (int i = 1; i <= 23; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}

for (auto& v : e[u]) {
self(self, v, u);
son[u] = std::max(son[u], son[v]);
}
};

dfs(dfs, 1, 1);

auto lca = [&](int x, int y)->int {
if (deep[x] < deep[y]) std::swap(x, y);

for (int i = 23; i >= 0; --i) {
if ((deep[x] - (1LL << i)) >= deep[y]) {
x = fa[x][i];
}
}

if (x == y) return x;

for (int i = 23; i >= 0; --i) {
if (fa[x][i] == fa[y][i]) continue;
x = fa[x][i], y = fa[y][i];
}
return fa[x][0];
};


std::vector<int>len(n + 1);
for (int i = 1; i <= n; ++i) {
len[i] = deep[i] + deep[i % n + 1] - 2 * deep[lca(i, i % n + 1)];
}

int res = n * w, sum = 0, s = 0;
for (int i = 1; i <= n - 1; ++i) {
int v, y;
std::cin >> v >> y;

int u = v - 1;
if (u == 0) u = n;

res -= (n - 2 - s) * y;
sum += y;

if (!--len[u]) {
res -= (w - sum);
++s;
}
if (!--len[son[v]]) {
res -= (w - sum);
++s;
}

std::cout << res << " ";
}
std::cout << "\n";

}

signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);

int t = 1;
std::cin >> t;

while (t--) {
solve();
}
};
``

原文地址：https://blog.csdn.net/Antonio915/article/details/142721256

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！