scratch网站开发,宿州公司做网站,wordpress首页错位,微信引流被加软件题目描述
Z 国的骑士团是一个很有势力的组织#xff0c;帮会中汇聚了来自各地的精英。他们劫富济贫#xff0c;惩恶扬善#xff0c;受到社会各界的赞扬。
最近发生了一件可怕的事情#xff0c;邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里#xff0c;在和平…题目描述
Z 国的骑士团是一个很有势力的组织帮会中汇聚了来自各地的精英。他们劫富济贫惩恶扬善受到社会各界的赞扬。
最近发生了一件可怕的事情邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上就像期待有一个真龙天子的降生带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士当然不是他自己他是绝对不会与自己最厌恶的人一同出征的。
战火绵延人民生灵涂炭组织起一个骑士军团加入战斗刻不容缓国王交给了你一个艰巨的任务从所有的骑士中选出一个骑士军团使得军团内没有矛盾的两人不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况并且使得这支骑士军团最具有战斗力。
为了描述战斗力我们将骑士按照 111 至 nnn 编号给每名骑士一个战斗力的估计一个军团的战斗力为所有骑士的战斗力总和。
输入格式
第一行包含一个整数 nnn描述骑士团的人数。
接下来 nnn 行每行两个整数按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出格式
应输出一行包含一个整数表示你所选出的骑士军团的战斗力。
输入输出样例 #1
输入 #1
3
10 2
20 3
30 1输出 #1
30说明/提示
数据规模与约定
对于 30%30\%30% 的测试数据满足 n≤10n \le 10n≤10
对于 60%60\%60% 的测试数据满足 n≤100n \le 100n≤100
对于 80%80\%80% 的测试数据满足 n≤104n \le 10 ^4n≤104。
对于 100%100\%100% 的测试数据满足 1≤n≤1061\le n \le 10^61≤n≤106每名骑士的战斗力都是不大于 10610^6106 的正整数。
solution
题目大意基环森林中不相邻点的距离和的最大值
思路
找到环上的某个点 u以 u 和其父节点 fa[u] 为根节点树上 dp 计算 f[i], g[i] ,即包含本节点的子树最大和和不含本节点的子树最大和结果为 ∑(max(g[u],g[fa[u]])\sum(max(g[u],g[fa[u]])∑(max(g[u],g[fa[u]]) 其中 u 为每个基环树中环上取一个点
代码#includeiostream
#includevector
#include algorithm
#include cstringusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N 1e6 5, M 1e9 7;int n, fa[N], vis[N], a[N];ll f[N], g[N];vectorint e[N];int find_u(int u) {vis[u] 1;return vis[fa[u]] ? u : find_u(fa[u]);
}void dp(int u, int p) {vis[u] 1;for (int v: e[u]) {if (v p) continue; // p 是起点相当于断开了起点和其fa的边dp(v, p);f[u] g[v];g[u] max(f[v], g[v]);}f[u] a[u];
}/** 1 反向建图形成外向基环树* 2 找到环上一个点 u, 以 u 为根节点进行树上 dp* f[u]:包含本节点的最大值* g[u]:不包含本节点的最大值* 3 以 fa[u] 为根节点进行树上 dp* max(g[u], g[fa])*/int main() {cin n;for (int i 1; i n; i) {scanf(%d%d, a i, fa i);// cin a[i] fa[i]; // 反向建图形成外向基环树e[fa[i]].push_back(i);}ll ans 0; for (int i 1; i n; i) {if (!vis[i]) {ll Max 0;int u find_u(i);dp(u, u);Max max(Max, g[u]);memset(f, 0, sizeof f);memset(g, 0, sizeof g);dp(fa[u], fa[u]);Max max(Max, g[fa[u]]);ans Max;}}cout ans endl;return 0;
}
结果
