帝国cms网站搬家,如何制作建筑公司网站,如何查看自己做的网站大小,网站建设哪家企业好E. Move and Swap
Heltion 由于红色硬币向下一层走的时候只能走儿子#xff0c;而蓝色无限制#xff08;对后续操作无影响#xff09;#xff0c;于是考虑下面表示
状态表示#xff1a;fuf_ufu表示当前是红色硬币#xff0c;向下一层走后的最大价值。 状态转移#…E. Move and Swap
Heltion 由于红色硬币向下一层走的时候只能走儿子而蓝色无限制对后续操作无影响于是考虑下面表示
状态表示fuf_ufu表示当前是红色硬币向下一层走后的最大价值。 状态转移 假设下一步走到儿子vvv并且不交换也就是vvv是红色硬币存在转移fufv∣av−am∣f_uf_v|a_v-a_m|fufv∣av−am∣mmm表示与vvv同层的那些节点
如果交换那么vvv就是蓝色硬币需要找到一个与vvv同层的节点mmm作为红色存在转移fufm∣av−am∣f_uf_m|a_v-a_m|fufm∣av−am∣
去掉绝对值预处理一些东西辅助转移即可v→uv\to uv→u我为人人转移
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
using lllong long;
constexpr int N200010;
constexpr ll INF0x3f3f3f3f3f3f3f3f;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;}
int d[N];
ll a[N];
vectorint g[N];
ll f[N];
int fa[N],n;
void dfs_d(int u)
{d[u]d[fa[u]]1;for(int ih[u];i!-1;ine[i]){int je[i];if(jfa[u]) continue;fa[j]u;dfs_d(j);}
}
void bfs(int S)
{for(int iS;i1;i--){// 不交换颜色u由儿子v转移ll vminINF,vmax-INF;for(int v:g[i]) vminmin(vmin,a[v]),vmaxmax(vmax,a[v]);for(int v:g[i]){int ufa[v];f[u]max(f[u],max(a[v]-vmin,vmax-a[v])f[v]);}// 交换颜色由同层节点转移ll p1-INF,p2-INF;for(int v:g[i]) p1max(p1,f[v]a[v]),p2max(p2,f[v]-a[v]);for(int v:g[i]){int ufa[v];f[u]max(f[u],p1-a[v]);f[u]max(f[u],p2a[v]);} }
}
void init(int n)
{memset(h,-1,(n1)*sizeof(int));idx0;memset(d,0,(n1)*sizeof(int));memset(fa,0,(n1)*sizeof(int));memset(f,0,(n1)*sizeof(ll));for(int i0;in;i) g[i].clear();
}
int main()
{IO;int T1;cinT;while(T--){cinn;init(n);for(int i2;in;i){int v;cinv;add(v,i),add(i,v);}for(int i2;in;i) cina[i];dfs_d(1);for(int i1;in;i) g[d[i]].push_back(i);bfs(*max_element(d1,d1n));coutf[1]\n;}return 0;
}写的时候状态定义不好导致不容易转移以后状态定义明确后在下手
