百度打开,上海最大的seo公司,网页设计模板素材代码,信阳建设企业网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
由于是按层来的#xff0c;所以我们肯定先按照层来分组。 定义dp[i]dp[i]dp[i]为红棋在位置iii的时候的最大得分和。 先考虑不换的情况#xff0c;我们对于每个点都从他的父节点转移过来…传送门
文章目录题意思路题意 思路
由于是按层来的所以我们肯定先按照层来分组。 定义dp[i]dp[i]dp[i]为红棋在位置iii的时候的最大得分和。 先考虑不换的情况我们对于每个点都从他的父节点转移过来就好了蓝棋由于可以到当前层的任意位置所以让他贪心的到最大或者最小位置一定是最优的我们取个maxmaxmax即可转移方程为dp[i]max(dp[i],dp[fa[i]]max(a[i]−mind,maxd−a[i]))dp[i]max(dp[i],dp[fa[i]]max(a[i]-mind,maxd-a[i]))dp[i]max(dp[i],dp[fa[i]]max(a[i]−mind,maxd−a[i])) 考虑我们如果将红黑交换这个操作实际上就是先将红棋移动到儿子节点让后让蓝棋移动到下一层再将其交换也即假设红棋原本在fa[k]fa[k]fa[k]现在应该到了kkk但是我们将其与位置iii的蓝棋换了位置所以当前位置应该在iii转移方程为dp[i]max(dp[i],dp[fa[k]]∣a[k]−a[i]∣)dp[i]max(dp[i],dp[fa[k]]|a[k]-a[i]|)dp[i]max(dp[i],dp[fa[k]]∣a[k]−a[i]∣) 这个转移不优化的话是n2n^2n2的考虑将绝对值去掉有两种情况a[k]a[i]a[k]a[i]a[k]a[i]和a[k]a[i]a[k]a[i]a[k]a[i]分别对应dp[fa[k]]a[k]−a[i]dp[fa[k]]a[k]-a[i]dp[fa[k]]a[k]−a[i]和dp[fa[k]]−a[k]a[i]dp[fa[k]]-a[k]a[i]dp[fa[k]]−a[k]a[i]考虑到dp[fa[k]]dp[fa[k]]dp[fa[k]]和a[k]a[k]a[k]是固定且绑定的所以我们可以预处理出最大的dp[fa[k]]a[k]dp[fa[k]]a[k]dp[fa[k]]a[k]和最大的dp[fa[k]]−a[k]dp[fa[k]]-a[k]dp[fa[k]]−a[k]让后O(1)O(1)O(1)转移即可复杂度为nnn的。
总体复杂度O(n)O(n)O(n)。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
vectorintv[N],depth[N];
int mx[N],mi[N],a[N],fa[N],d[N];
LL f[N];void dfs_depth(int u,int f,int d)
{fa[u]f;depth[d].pb(u);mx[d]max(mx[d],a[u]);mi[d]min(mi[d],a[u]);for(auto x:v[u]){if(xf) continue;dfs_depth(x,u,d1);}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--){scanf(%d,n);for(int i1;in;i) v[i].clear(),depth[i].clear(),mx[i]0,mi[i]INF,f[i]0;for(int i2;in;i) {int x; scanf(%d,x);v[i].pb(x); v[x].pb(i);}for(int i2;in;i) scanf(%d,a[i]);dfs_depth(1,0,1);LL ans0;for(int i2;in;i){LL mxa-INF,mxb-INF;for(auto x:depth[i]){mxamax(mxa,f[fa[x]]a[x]);mxbmax(mxb,f[fa[x]]-a[x]);}for(auto x:depth[i]){f[x]max(f[x],f[fa[x]]max(mx[i]-a[x],a[x]-mi[i]));f[x]max(f[x],max(mxa-a[x],mxba[x]));ansmax(ans,f[x]);}}printf(%lld\n,ans);}return 0;
}
/**/
