洛谷P3574(POI 2014)
题目描述
在一个叫做比特村的小村庄中,有 \(n-1\) 条路连接着这个村庄中的全部 \(n\) 个房子。
每两个房子之间都有一条唯一的通路。这些房子的编号为 \(1\) 至 \(n\)。
\(1\) 号房子属于村庄的管理员比特安萨尔。
为了提升村庄的科技使用水平,\(n\) 台电脑被快递到了比特安萨尔的房子。每个房子都应该有一台电脑,且分发电脑的任务就落在了比特安萨尔的肩上。
比特村的居民一致同意去玩农场物语这个游戏的最新快照版,而且好消息是他们很快就要得到他们最新的高配置电脑了。
比特安萨尔将所有电脑都装在了他的卡车上,而且他准备好完成这个艰巨的任务了。
他的汽油恰好够走每条路两遍。
在每个房子边,比特安萨尔把电脑贴心的配送给居民,且立即前往下一个房子。(配送过程不花费任何时间)
只要每间房子的居民拿到了他们的新电脑,它们就会立即开始安装农场物语。安装农场物语所用的时间根据居民的科技素养而定。幸运的是,每间房子中居民的科技素养都是已知的。
在比特安萨尔配送完所有电脑后,他会回到他自己的 \(1\) 号房子去安装他自己的农场物语。
用卡车开过每条路的时间恰好是 \(1\) 分钟,而居民开电脑箱的时间可以忽略不计。(因为他们太想玩农场物语了)
请你帮助比特安萨尔算出从开始配送到所有居民都玩上了农场物语的最少时间。
输入格式
第一行包含一个整数 \(n(2 \leq n \leq 5\times 10^5)\),代表比特村中有多少房子。
第二行包含 \(n\) 个整数 \(c_1, c_2, ⋯, c_n(1 \leq c_i \leq 10^9)\),每个数都被单个空格隔开。\(c_i\) 是第 \(i\) 号房间中居民安装农场物语所用的时间。
接下来的 \(n-1\) 行代表了每一条路的两个顶点。两个顶点 \(a\) 和 \(b\) 满足 \(1 \leq a < b \leq n\),两个数之间有一个空格。
输出格式
一行,包含一个整数,代表题目中所说的最小时间。
题解
一道很显然的树形DP。
设状态\(f_i\)代表走完以i为根子树中的最大时间。
便可以很显然的得出转移方程:\(f_i = max( f_j + t +1)\),其中\(j\)为\(i\)的儿子,\(t\)为开始往\(j\)走时的时间。
接下来开始推转移顺序。
设\(size_u\)为走完以u为根的子树所需的时间。
令树上任意一点p的其中两个儿子为\(x\)和\(y\)
若令x先走,则\(f_p\)=\(max(f_p,t+max(f_x,f_y+size_x+2)+1)\)
反之,则\(f_p\)=\(max(f_p,t+max(f_y,f_x+size_y+2)+1)\)
则可得当让x先转移更优时,当且仅当\(size_x\)-\(f_x\)<\(size_y\)-\(f_y\)
便可以按照此式给每个点的所有儿子排序以确定转移顺序
Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 7;
struct edge{int to, pre;
}e[N << 1];
int n;
ll w[N];
int head[N], tot;
vector<int>son[N];
ll f[N];
int size[N];
void add(int x, int y){e[++tot] = {y, head[x]};head[x] = tot;
}
void dfs1(int u, int fa){for(int i = head[u]; i; i = e[i].pre){int v = e[i].to;if(fa == v) continue;son[u].push_back(v);dfs1(v, u);}
}
bool cmp(int x, int y){return size[x] - f[x] < size[y] - f[y];
}
void dfs2(int u){if(u != 1) f[u] = w[u];int len = son[u].size();for(int i = 0; i < len; i++){int v = son[u][i];dfs2(v);}sort(son[u].begin(), son[u].end(), cmp);for(int i = 0; i < len; i++){int v = son[u][i];f[u] = max(f[u], f[v] + size[u] + 1);size[u] += size[v] + 2;}
}
int main(){scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%lld", &w[i]);}for(int i = 1; i < n; i++){int x, y;scanf("%d%d", &x, &y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1);printf("%lld\n", max(f[1], size[1] + w[1]));return 0;
}
P3177 [HAOI2015] 树上染色
题目描述
有一棵点数为 \(n\) 的树,树边有边权。给你一个在 \(0 \sim n\) 之内的正整数 \(k\) ,你要在这棵树中选择 \(k\) 个点,将其染成黑色,并将其他的 \(n-k\) 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。
输入格式
第一行包含两个整数 \(n,k\)。
第二到 \(n\) 行每行三个正整数 \(u, v, w\),表示该树中存在一条长度为 \(w\) 的边 \((u, v)\)。输入保证所有点之间是联通的。
输出格式
输出一个正整数,表示收益的最大值。
说明/提示
对于 \(100\%\) 的数据,\(0 \leq n,k \leq 2000\)。
题解
这也是一道很显然的树形dp。
设状态\(f_{i,j}\)为在以\(i\)为根的子树内染上\(j\)个黑点对答案产生的贡献。
接下来去考虑转移,
对于树上的每个节点\(u\)
记其子树内黑点数量为\(b_u\),白点数量为\(w_u\),子树大小为\(size_u\),连接结点\(u,v\)的边的权值为\(e_{u,v}\)
考虑遍历\(u\)的每个子树
对于\(u\)的每个子树\(v\)
因为每一对分别在\(v\)子树内外的同色点对都会经历连接\(u,v\)的这条边
其与外界产生的贡献即为\(num=(b_v\times (k-b_v)+w_v \times ((n-k)-w_v) \times e_{u,v}\)
再结合\(v\)子树内的贡献
可得转移方程为\(f_{u,p+q}=\max(f_{u,p+q},f_{u,p}+f_{v,q}+num)\)
时间复杂度为\(O(n^3)\)
接下来考虑优化
可将\(p\)的枚举上界优化为\(\min(k,size[u])\),\(q\)的枚举上界优化为\(\min(k-p,size[v])\)
此时可以证明时间复杂度近似\(O(n^2)\)
时间复杂度的完整分析
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 2007;
#define ll long long
struct edge{int to, w, pre;
}e[N << 1];
int n, k;
int head[N], tot;
int size[N];
ll dp[N][N];
void add(int x, int y, int z){e[++tot] = {y, z, head[x]};head[x] = tot;
}
void dfs(int u, int fa){size[u] = 1;for(int i = head[u]; i; i = e[i].pre){int v = e[i].to;if(fa == v) continue;dfs(v, u);for(int p = min(k, size[u]); p >= 0; p--){for(int q = 0; q <= min(k - p, size[v]); q++){ll w = 1ll * e[i].w * (q * (k - q) + ((n - k) - (size[v] - q)) * (size[v] - q));dp[u][p + q] = max(dp[u][p + q], dp[u][p] + dp[v][q] + w);}}size[u] += size[v]; }
}
int main(){scanf("%d%d", &n, &k);for(int i = 1; i < n; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);add(u, v, w);add(v, u, w);}dfs(1, 0);printf("%lld\n", dp[1][k]);return 0;
}
CF708C Centroids
CF708C Centroids
题目描述
树 是一种连通的无环图。假设给定一棵由 \(n\) 个顶点组成的树。如果移除该顶点后,树中每个连通分量的大小均不超过 \(\frac{n}{2}\),则该顶点被称为重心。
给定一棵大小为 \(n\) 的树,你可以执行最多一次边的替换操作。边的替换操作指的是从树中移除一条边(不删除相邻顶点)并插入一条新边(不添加新顶点),使得图仍保持为一棵树。对于每个顶点,你需要判断是否可以通过执行最多一次边的替换操作使其成为重心。
输入格式
输入的第一行包含一个整数 \(n\)(\(2 \le n \le 400000\))——树中顶点的数量。接下来的 \(n-1\) 行中,每行包含两个顶点索引 \(u_i\) 和 \(v_i\)(\(1 \le u_i, v_i \le n\)),表示对应边的两个端点。
输出格式
输出 \(n\) 个整数。第 \(i\) 个整数应为 \(1\) 如果可以通过替换不超过一条边使第 \(i\) 个顶点成为重心,否则应为 \(0\)。
题解
当一个点\(u\)不是重心,则可得此点的某个子树的节点数量\(>\frac{n}{2}\)。
但这是一棵无根树
因此这个子树可能是\(u\)的祖先
这样会使我们的计算变得十分混乱
因此我们可以钦定以\(1\)号点为根的树上的重心为根
这样对于每个点\(u\),不符合要求的子树仅有可能是其祖先
那么我们便可以将其祖先的最大的符合要求的子树移植到这个点上使得祖先子树的大小变小
记以\(u\)为根的子树大小为\(size_u\),树上除了以\(u\)为根的子树内的结点外符合要求的子树中大小最大的子树大小为\(cut_u\)
那么一个点可通过一次修改操作成为重心当且仅当\(n-size[u]-cut[u]<=\frac{n}{2}\)
为什么呢?
因为上面的式子表示的是移植子树后,以其父亲为根的子树的大小
且这个子树是唯一可能不符合要求的子树
那么问题便转化为了求\(cut_u\)
\(cut_u\)有\(2\)种存在的方式
要么是\(u\)的祖先,要么是\(u\)的兄弟
我们可以在\(DFS\)中加一个参数\(res\)来表示\(cut_u\)
对于第一种情况,
我们访问点\(u\)时,
若\(n-size_u<=\frac{n}{2}\)
则\(res=\max(res,n-size_u)\)
对于第二种情况,
我们维护一个数组\(max_{u,0/1}\)代表以\(u\)为根的子树内子树大小的最大/次大值
枚举每个儿子\(v\)
若\(size_v<max_{u,0}\),则\(res=max(res,max_{u,0})\)
否则,\(res=max(res,max_{u,1})\)
再在每次访问开始时将\(res\)赋值给\(cut_u\)
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 7;
#define ll long long
struct edge{int to, pre;
}e[N << 1];
int n;
int head[N], tot;
int sizee[N], rt;
int mxx[N][2], cut[N];
bool ans[N];
int ft[N];
void add(int x, int y){e[++tot] = {y, head[x]};head[x] = tot;
}
void dfs1(int u, int fa){bool flg = 0;sizee[u] = 1;for(int i = head[u]; i; i = e[i].pre){int v = e[i].to;if(fa == v) continue;dfs1(v, u);sizee[u] += sizee[v]; if(sizee[v] > n / 2) flg = 1;}if(n - sizee[u] > n / 2) flg = 1;if(!flg) rt = u;
}
void dfs2(int u, int fa){ft[u] = fa;sizee[u] = 1;for(int i = head[u]; i; i = e[i].pre){int v = e[i].to;if(ft[u] == v) continue;dfs2(v, u);sizee[u] += sizee[v];if(sizee[v] > n / 2) continue;if(sizee[v] > mxx[u][0]){mxx[u][1] = mxx[u][0];mxx[u][0] = sizee[v]; }else{if(sizee[v] > mxx[u][1]){mxx[u][1] = sizee[v];}}}
}
void dfs3(int u, int res){cut[u] = res;if(n - sizee[u] <= n / 2) res = max(res, n - sizee[u]);for(int i = head[u]; i; i = e[i].pre){int v = e[i].to;if(ft[u] == v) continue;if(mxx[u][0] == sizee[v]) dfs3(v, max(res, mxx[u][1]));else dfs3(v, max(res, mxx[u][0]));}if(n - sizee[u] - cut[u] <= n / 2 || u == rt) ans[u] = 1;
// printf("%d:%d %d\n", u, res, cut[u]);
}
int main(){scanf("%d", &n);for(int i = 1; i < n; i++){int u, v;scanf("%d%d", &u, &v);add(u, v);add(v, u);}dfs1(1, 0);memset(sizee, 0, sizeof(sizee));dfs2(rt, 0);dfs3(rt, 0);for(int i = 1; i <= n; i++) printf("%d ", ans[i]);putchar('\n');return 0;
}