卓越建站快车,做企业网站的公司,wordpress显示中文乱码,中职计算机网站建设教学计划登录—专业IT笔试面试备考平台_牛客网
题意 思路
首先想法非常单一#xff0c;一定是去枚举操作点#xff0c;然后看它染白和不染的价值差值
也就是说#xff0c;把一个黑色结点染白之后#xff0c;对哪些结点的价值会影响
不难想象其实就是操作结点的子树和该点连通的…登录—专业IT笔试面试备考平台_牛客网
题意 思路
首先想法非常单一一定是去枚举操作点然后看它染白和不染的价值差值
也就是说把一个黑色结点染白之后对哪些结点的价值会影响
不难想象其实就是操作结点的子树和该点连通的黑色连通块的所有结点对这些结点会有影响
那么差值其实就是黑色连通块大小 * 操作点到最近的白色祖先的距离
黑色连通块容易用树形dp求然后就是操作点到最近白色祖先距离怎么求
dfs即可记录上次的白色结点是什么即可
#include bits/stdc.h#define int long longconstexpr int N 2e5 10;std::vectorint adj[N];int n;
int a[N];
int lst[N];
int sz[N], dep[N], F[N][33];
int dp[N];void dfs(int u, int fa) {sz[u] 1;dep[u] dep[fa] 1;F[u][0] fa;for (int i 1; i 30; i) {F[u][i] F[F[u][i - 1]][i - 1];}for (auto v : adj[u]) {if (v fa) continue;dfs(v, u);sz[u] sz[v];}
}
void dfs2(int u, int fa) {if (a[u] 1) dp[u] 1;for (auto v : adj[u]) {if (v fa) continue;dfs2(v, u);if (a[v] 1) {dp[u] dp[v];}}
}
void dfs3(int u, int fa, int last) {lst[u] last;for (auto v : adj[u]) {if (v fa) continue;int clst 0;if (a[v]) {clst last;}else {clst v;}dfs3(v, u, clst); }
}
int lca(int u, int v) {if (dep[u] dep[v]) {std::swap(u, v);}for (int j 30; j 0; j --) {if (dep[F[u][j]] dep[v]) {u F[u][j];} }if (u v) return u;for (int j 30; j 0; j --) {if (F[u][j] ! F[v][j]) {u F[u][j];v F[v][j];}}return F[u][0];
}
int dis(int u, int v) {return dep[u] dep[v] - 2 * dep[lca(u, v)];
}void solve() {std::cin n;for (int i 1; i n; i ) {std::cin a[i];}for (int i 1; i n - 1; i ) {int u, v;std::cin u v;adj[u].push_back(v);adj[v].push_back(u);}dfs(1, 0);dfs3(1, 0, 1);for (int i 1; i n; i ) {lst[i] dis(i, lst[i]);}dfs2(1, 0);int cur 0;for (int u 1; u n; u ) {if (a[u] 1) {cur lst[u];}}int ans cur;for (int u 1; u n; u ) {if (!a[u]) continue;int res cur;res - dp[u] * lst[u];ans std::min(ans, res);}std::cout ans \n;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;while(t --) {solve();}return 0;
}
