h5网站建设文章,广州外贸soho建站,深圳外贸网站优化,手机网站开放树上游戏
给定一棵 nnn 个节点的树#xff0c;点从 111 到 nnn 编号#xff0c;点有点权#xff0c;边有边权#xff0c; Alice\text{Alice}Alice 和 Bob\text{Bob}Bob 两人在做游戏。
棋子以某一个点 sss 为起点#xff0c;玩家移动该棋子#xff0c;有以下两条规则点从 111 到 nnn 编号点有点权边有边权 Alice\text{Alice}Alice 和 Bob\text{Bob}Bob 两人在做游戏。
棋子以某一个点 sss 为起点玩家移动该棋子有以下两条规则
移动时不能经过已经走过的边能移动则必须移动不能在可移动时停留在原地
由 Alice\text{Alice}Alice 开始轮流移动棋子最终的得分为经过的点权之和减去经过的边权之和。
Alice\text{Alice}Alice 想要最大化得分 Bob\text{Bob}Bob 想要最小化得分假设两人都采取最优策略那么最终得分是多少呢
请你对于每个点为起点都输出一个答案。 1≤n≤105,∣vi∣,∣wi∣≤1091\le n\le 10^5,\vert v_i\vert,\ \vert w_i\vert \le 10^91≤n≤105,∣vi∣, ∣wi∣≤109 不难发现当起点确定时可以通过如下树形dp确定结果
状态表示fu,0/1f_{u,0/1}fu,0/1以uuu为起点向子树中移动当前该Alice/Bob\text{Alice}/\text{Bob}Alice/Bob最终的值 状态转移 下面valu\text{val}_uvalu表示uuu的点权wiw_iwi表示u→vu\to vu→v的边权
Alice\text{Alice}Alice需要让结果尽可能大fu,0maxv∈sonu(fv,1valu−wi)f_{u,0}\max_{v\in \text{son}_u}(f_{v,1}\text{val}_u-w_i)fu,0maxv∈sonu(fv,1valu−wi)Bob\text{Bob}Bob需要让结果尽可能小fu,1minv∈sonu(fv,0valu−wi)f_{u,1}\min_{v\in \text{son}_u}(f_{v,0}\text{val}_u-w_i)fu,1minv∈sonu(fv,0valu−wi)
注意在叶子节点进行初始化
由于存在换根操作不难发现只要记录fu,0f_{u,0}fu,0的最大次大值以及fu,1f_{u,1}fu,1的最小次小值即可从父节点更新子节点实现换根操作。 注意这种情况 当前根是uuu准备换根到vvv我们需要让uuu的信息去更新vvv的信息如果vvv在树中是叶子节点需要特殊地将uuu的信息直接赋给vvv而不是更新因为vvv是叶子节点在以uuu为根时走到vvv就会停止而在以vvv为根时并不会停止并且一定会向uuu移动
还有在第一遍dfs时不能以入度为1的点为根进行dfs因为这个点在其他点为根的时是叶子节点某些信息会错误更新比如下面数据
5
2147483647 2147483647 2147483647 2147483647 -2147483647
1 2 2147483647
2 3 2147483647
3 4 2147483647
4 5 2147483647总的来说需要注意叶子节点的信息的更新
#includecstring
#includeiostream
#includealgorithm
using namespace std;
using lllong long;
constexpr int N100010;
constexpr ll INF0x3f3f3f3f3f3f3f3f;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
void add(int a,int b,int c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;}
int val[N],n;
ll f[N][2],g[N][2],ans[N];// f[u][0/1]表示u子树 该A/B移动
int fr[N][2];
int d[N];
bool leaf[N];
void update(int u,int k,int v,ll x)// 更新 最大次大/最小次小
{if(k0){if(xf[u][k]) {g[u][k]f[u][k];f[u][k]x;fr[u][k]v;}else if(xg[u][k]) g[u][k]x;}else{if(xf[u][k]){g[u][k]f[u][k];f[u][k]x;fr[u][k]v;}else if(xg[u][k]) g[u][k]x;}
}
void dfs1(int u,int fa)
{leaf[u]1;for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;leaf[u]0;dfs1(v,u);for(int k0;k1;k)update(u,k,v,f[v][k^1]val[u]-w[i]);}if(leaf[u]) f[u][0]f[u][1]val[u];//叶子节点初值
}
void dfs2(int u,int fa)
{ans[u]f[u][0];for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;for(int k0;k1;k){if(leaf[v])//叶子节点特殊处理{if(fr[u][k]v) f[v][k^1]g[u][k]val[v]-w[i];else f[v][k^1]f[u][k]val[v]-w[i];}else//换根{if(fr[u][k]v) update(v,k^1,u,g[u][k]val[v]-w[i]);elseupdate(v,k^1,u,f[u][k]val[v]-w[i]);}}dfs2(v,u);}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;memset(h,-1,sizeof h);for(int i1;in;i) cinval[i];for(int i1;in;i) f[i][0]g[i][0]-INF,f[i][1]g[i][1]INF;for(int i1;in;i){int a,b,c;cinabc;add(a,b,c),add(b,a,c);d[a],d[b];}int rt1;while(d[rt]1) rt;//找一个度数不为1的为根dfs1(rt,0);dfs2(rt,0);for(int i1;in;i) coutans[i]\n;
}这题我一共写了4次 第一次比赛口胡 第二次赛后写代码没过懒得调了 第三次2021/01/04刚放寒假重新写没注意叶子的细节一直没过 第四次2021/02/25快开学了准备吧收藏夹的题补一补有看见这个题造了造特数数据发现了代码问题注意到叶子细节成功AC经历2.5h
终于把这题干掉了 要加油哦~
