題面：不存在的

我們先dfs一次，只保留每個分叉最上面的顏色，并求到根的前綴和，這就是每個點到根的和，記為s1，然后我們求子樹里的，這里只保留了最上面的顏色，那么我們求樹鏈的并，做樹上前綴和，這就是子樹顏色的和，記為s2，s1+s2就是子樹和到根顏色的并，因為只保留了最上層的顏色，也就是說對于一個點，某種顏色只會存在在子樹中或到根的路徑上，不會重復統計，然后是風，我們先dfs一遍計算出訪問序列，然后樹上差分，如果這兩個點是a和b，且a的訪問時間早于b，那么我們讓a=fa[a][0],因為size[u]-1，所以自然是第一個訪問的不算，然后就是按訪問順序加入每個點的貢獻，計算答案就行了。

這道題集合了很多樹上方法，值得一做

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 5; struct edge {int nxt, to; } e[N << 1]; int n, m, top, dfs_clock, cnt = 1, C; ll ans, sum; int mir[N], head[N], vis[N], in[N], out[N], a[N], fa[N][21], tim[N], val[N], st[N], dep[N]; vector<int> G[N], c[N]; ll s1[N], s2[N], s3[N]; bool cmp1(const int &i, const int &j) {return val[i] < val[j]; } bool cmp2(const int &i, const int &j) {return in[i] < in[j]; } void link(int u, int v) {e[++cnt].nxt = head[u];head[u] = cnt;e[cnt].to = v; } void dfs(int u, int last) {in[u] = ++dfs_clock;mir[in[u]] = u;val[u] = u;if(!vis[a[u]]) vis[a[u]] = 1, ++s1[u];else a[u] = 0;for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last) {G[u].push_back(e[i].to);fa[e[i].to][0] = u;dep[e[i].to] = dep[u] + 1;s1[e[i].to] += s1[u];dfs(e[i].to, u);val[u] = min(val[u], val[e[i].to]);}sort(G[u].begin(), G[u].end(), cmp1);vis[a[u]] = 0;out[u] = dfs_clock; } int lca(int u, int v) {if(dep[u] < dep[v]) swap(u, v);int d = dep[u] - dep[v];for(int i = 20; i >= 0; --i) if(d & (1 << i)) u = fa[u][i];if(u == v) return u;for(int i = 20; i >= 0; --i) if(fa[u][i] != fa[v][i]) {u = fa[u][i];v = fa[v][i];}return fa[u][0]; } void dfs(int u) {if(a[u]) c[a[u]].push_back(u);for(int i = 0; i < G[u].size(); ++i) {int v = G[u][i];dfs(v);}st[++top] = u;tim[u] = top; } int main() {scanf("%d%d%d", &n, &m, &C);for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);for(int i = 1; i < n; ++i){int u, v;scanf("%d%d", &u, &v);link(u, v);link(v, u);}dfs(1, 0);for(int j = 1; j <= 20; ++j)for(int i = 1; i <= n; ++i)fa[i][j] = fa[fa[i][j - 1]][j - 1];dfs(1);for(int i = 1; i <= C; ++i) if(c[i].size()) {sort(c[i].begin(), c[i].end(), cmp2);++s2[in[c[i][0]]];for(int j = 1; j < c[i].size(); ++j) {int x = lca(c[i][j - 1], c[i][j]);--s2[in[x]];++s2[in[c[i][j]]];}}for(int i = 1; i <= m; ++i){int x, y, z, t;scanf("%d%d%d", &x, &y, &z);t = lca(x, y);if(tim[x] > tim[y]) swap(x, y);x = fa[x][0];s3[in[x]] += z;s3[in[y]] += z;s3[in[t]] -= z;s3[in[fa[t][0]]] -= z; }for(int i = 1; i <= n; ++i) s2[i] += s2[i - 1], s3[i] += s3[i - 1];for(int i = 1; i <= top; ++i) { // printf("st[%d] = %d\n", i, st[i]);ll d1 = s2[out[st[i]]] - s2[in[st[i]] - 1], d2 = s3[out[st[i]]] - s3[in[st[i]] - 1];sum += s1[fa[st[i]][0]] + s2[out[st[i]]] - s2[in[st[i]] - 1] + s3[out[st[i]]] - s3[in[st[i]] - 1] - dep[st[i]];ans = max(ans, sum); }printf("%lld\n", ans);return 0; } View Code

?

轉載于:https://www.cnblogs.com/19992147orz/p/7773105.html

總結

以上是生活随笔為你收集整理的听风的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。