HDU 6662 Acesrc and Travel (换根dp)
However, Zhang and Liu have different preferences for these spots. They respectively set a satisfactory value for each spot. If they visit the ith spot, Zhang will obtain satisfactory value ai, and Liu will obtain bi. Starting with Zhang, they alternately decide the next spot to visit for the sake of fairness. There must be a bus route between the current spot and the next spot to visit. Moreover, they would never like to visit a spot twice. If anyone can't find such a next spot to visit, they have no choice but to end this travel.
Zhang and Liu are both super smart competitive programmers. Either want to maximize the difference between his total satisfactory value and the other's. Now Acesrc wonders, if they both choose optimally, what is the difference between total satisfactory values of Zhang and Liu?
For each test case, the first line contains a single integer n (1≤n≤105), denoting the number of spots. Each of the next two lines contains n integers, a1,a2,⋯,anand b1,b2,⋯,bn (0≤ai,bi≤109), denoting the
satisfactory value of Zhang and Liu for every spot, respectively. Each of the last n−1 lines contains two integers x,y (1≤x,y≤n,x≠y), denoting a bus route between the xth spot and the yth spot. It is reachable from any spot to any other spot through these bus routes.
It is guaranteed that the sum of n does not exceed 5.01×105.
3
1 1 1
0 2 3
1 2
1 3
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime> #define fuck(x) cerr<<#x<<" = "<<x<<endl;
#define debug(a, x) cerr<<#a<<"["<<x<<"] = "<<a[x]<<endl;
#define lson l,mid,ls
#define rson mid+1,r,rs
#define ls (rt<<1)
#define rs ((rt<<1)|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int loveisblue = ;
const int maxn = ;
const int maxm = ;
const ll Inf = 0x3f3f3f3f3f3f3f3f;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-); int Head[maxn], cnt;
struct edge {
int Next, v;
} e[maxm]; void add_edge(int u, int v) {
e[cnt].Next = Head[u];
e[cnt].v = v;
Head[u] = cnt++;
} ll a[maxn]; ll dp1[][maxn];//0由第一个人选择而来,1第二个选择而来
ll dp2[][maxn];//次
bool vis[maxn]; void dfs(int u, int fa) {
bool flag = true;
for (int k = Head[u]; k != -; k = e[k].Next) {
if (e[k].v == fa) {
continue;
}
dfs(e[k].v, u);
flag = false; ll tmp1 = dp1[][e[k].v];
ll tmp0 = dp1[][e[k].v]; //当前由第一个人选择而来的,那下一个一定由第二个人选择而来
if (tmp1 < dp2[][u]) { swap(tmp1, dp2[][u]); }
if (dp2[][u] < dp1[][u]) { swap(dp2[][u], dp1[][u]); } if (tmp0 > dp2[][u]) { swap(tmp0, dp2[][u]); }
if (dp2[][u] > dp1[][u]) { swap(dp2[][u], dp1[][u]); }
} vis[u] = flag;
//叶子节点的特殊处理
if (flag) {
dp1[][u] = ;
dp1[][u] = ;
}
if (dp1[][u] != Inf) dp1[][u] += a[u];
if (dp1[][u] != -Inf) dp1[][u] += a[u];
if (dp2[][u] != Inf) dp2[][u] += a[u];
if (dp2[][u] != -Inf) dp2[][u] += a[u];
} ll ans = -Inf; void dfs1(int u, int fa) { ll tmp0 = dp1[][fa];
ll tmp1 = dp1[][fa]; //如果父亲节点的最值是由u转移来的,那么就要利用次值换根
if (tmp0 == dp1[][u] + a[fa]) {
tmp0 = dp2[][fa];
}
if (tmp1 == dp1[][u] + a[fa]) {
tmp1 = dp2[][fa];
} //如果fa是只有u这一个儿子,并且fa==1时,才会出现这种情况
if (tmp1 == -Inf) {
tmp1 = a[fa];
}
if (tmp0 == Inf) {
tmp0 = a[fa];
}
tmp0 += a[u];
tmp1 += a[u]; //u是叶子节点,直接特判
if (vis[u]) {
ans = max(ans, tmp1);
}
//此段代码和dfs中的完全相同
if (tmp1 < dp2[][u]) { swap(tmp1, dp2[][u]); }
if (dp2[][u] < dp1[][u]) { swap(dp2[][u], dp1[][u]); } if (tmp0 > dp2[][u]) { swap(tmp0, dp2[][u]); }
if (dp2[][u] > dp1[][u]) { swap(dp2[][u], dp1[][u]); } ans = max(ans, dp1[][u]); for (int k = Head[u]; k != -; k = e[k].Next) {
if (e[k].v != fa)dfs1(e[k].v, u);
}
} int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--) {
int n;
ans = -Inf;
cnt = ;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
Head[i] = -;
scanf("%lld", &a[i]);
dp1[][i] = dp2[][i] = Inf;
dp1[][i] = dp2[][i] = -Inf; }
for (int i = ; i <= n; i++) {
ll x;
scanf("%lld", &x);
a[i] -= x;
}
for (int i = ; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
add_edge(x, y);
add_edge(y, x);
}
dfs(, );
ans = dp1[][];
for (int k = Head[]; k != -; k = e[k].Next) {
dfs1(e[k].v, );
}
printf("%lld\n", ans);
}
return ;
}
对代码有问题可以留言
最新文章
- 前端项目通用、常用js common.js
- mac显示和隐藏文件
- andriod 手机按键检测事件 onKeyDown() 简述
- 让我轻轻的告诉你AliSQLselect语句中in多少个合适
- Eclipse 安装需要的 JDK 版本简要说明
- wechat开发
- RabbitMQ驱动简单例子
- MONGODB(三)——Java操作Mongo
- Revit二次开发示例:DesignOptions
- php解压zip文件
- py2.7+pyqt4开发端口检测工具
- 【同行说技术】iOS程序员从小白到大神必读资料汇总
- mysql外键级联更新删除
- ubuntu下android源码下载
- WinPcap编程入门实践
- Arcgis Engine 添加一个Symbol符号样式步骤
- Android进程内存上限
- zoj2112 树状数组+主席树 区间动第k大
- pypi pack and upload
- 在Qt项目中添加全局宏变量来达到按方案编译的目的