题目大意

现在有一棵树，每条边可以为虚或为实，但是在任何时刻任何一个点的所有向下的边中最多只能有一条实边。初始虚实关系由你决定。

现在有 ​qqq 个要求，要你在 35​ 步操作内令 ​uuu 到根的路径变为全是实边。（达成目标后，你仍可继续操作，只要保证结束时仍满足要求即可）

各要求之间不独立。（你上一个要求的结束状态会沿袭到下一个要求的起始状态。）

SOLUTION

重链剖分

首先我们将重边设为实边

三种转移（选择最优（也就是最大步数最小）的一种）

• 最先设定重儿子

  • 若当前是重儿子，需要0步

  • 若当前是轻儿子，需要4步：将重儿子取消，改为ta，将ta取消，改回重儿子

• 全部不设定重儿子，需要2步：将重儿子设ta，将ta取消

• 最先不设定重儿子

  • 若当前重儿子，需要1步：将重儿子设为ta

  • 若当前轻儿子，需要3步：将重儿子取消，将重儿子设ta，将ta取消

我们使用dp[i][j]dp[i][j]dp[i][j]表示到第iii个点使用第jjj种转移的最大步数

然后在initinitinit时确定使用哪一种方式

并做好（设/不设 重儿子 的）处理

CODE

#include
#include"river.h"
const int N=1e5+2;
int fa[N],son[N],kd[N],vis[N],top[N],dp[N][4],sz[N],to[N],nxt[N],hd[N],cnt;
void add(int x,int y){to[++cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt;
}
void dfs(int x){sz[x]=1; son[x]=-1;for(int i=hd[x];i;i=nxt[i]){int y=to[i];fa[y]=x;dfs(y);sz[x]+=sz[y];if(sz[y]>sz[son[x]]||son[x]==-1)son[x]=y;}int mx=0;for(int i=hd[x];i;i=nxt[i]){int y=to[i];if(y==son[x]) continue; mx=std::max(mx,dp[y][kd[y]]);}dp[x][1]=std::max(mx+4,dp[son[x]][kd[son[x]]]);//重儿子 dp[x][2]=std::max(mx+2,dp[son[x]][kd[son[x]]]+2);dp[x][3]=std::max(mx+3,dp[son[x]][kd[son[x]]]+1);int mn=std::min({dp[x][1],dp[x][2],dp[x][3]});if(mn==dp[x][1])kd[x]=1;else if(mn==dp[x][2])kd[x]=2;else if(mn==dp[x][3])kd[x]=3;
}
void dfs(int x,int t){//重链剖分 top[x]=t;if(son[x]==-1)return;if(kd[x]==1)dfs(son[x],t);else dfs(son[x],son[x]);for(int i=hd[x];i;i=nxt[i]){int y=to[i];if(y==son[x]) continue; dfs(y,y);}
}
std::vector init(int n, std::vector father){for(int i=0;i<=n-2;i++){add(father[i],i+2);}//知道了爸爸，只见一条边即可 dfs(1);dfs(1,1);std::vector H(n,0);for(int i=1;i<=n;i++){if(kd[i]==1){H[i-1]=son[i];//指定重儿子 }} return H;
}
void prepare(int x){int now=x;while(fa[now]){//为下次做准备 if(kd[fa[now]]==1){//保持正常重儿子 if(now!=son[fa[now]]){//如果不是重儿子的话 set(fa[now],0);set(fa[now],son[fa[now]]);}}else if(kd[fa[now]]==2){//保证一直没有重儿子 set(fa[now],0);}else{if(vis[fa[now]]){if(now!=son[fa[now]]){set(fa[now],0);vis[fa[now]]=0;}}else{if(now==son[fa[now]])vis[fa[now]]=1;else set(fa[now],0);} }now=top[fa[now]];}
}
void solve(int x){int now=x;while(fa[now]){if(kd[fa[now]]==1){if(now!=son[fa[now]]){set(fa[now],0);set(fa[now],now);}}else if(kd[fa[now]]==2){set(fa[now],now);}else{if(vis[fa[now]]){if(now!=son[fa[now]]){set(fa[now],0);set(fa[now],now);}}else{set(fa[now],now);}}now=top[fa[now]];}wait();prepare(x);//为下一次做准备 
}

完结撒花❀

★,°:.☆(￣▽￣)/$:.°★ 。