2025.8.21
NOIP 模拟赛。预估是 \(100+30+50+20=200\)，实际 \(100+30+40+20=190\)，T3 挂分的原因是写了一个程序运行超过 0.95s 就自动输出无解的一个卡时语句，结果直接给我送走 10pts……警钟长鸣
A. 函数
可以发现原来的 \(f(n)\) 实际上就是欧拉函数 \(\varphi(n)\)，然后写一个线性筛 \(O(n)\) 预处理欧拉函数的做法就完了。
B. 创世纪
这题在校内集训的官方题解是贪心，然后我的这个断环 DP 做法调了六个小时
首先如果把这个限制与被限制的关系连上边的话，可以发现连成了若干基环树。遇到基环树一般的做法有两种：
- 首先把环的边全部断开，变成若干棵以环上的点为根结点树，然后就可以转化成树上问题，最后我们就可以得到环上每一个结点的信息，问题就变成环上问题了。
- （个人常用）我们可以发现基环树实际上就是一棵树多了一条边 \((lt,rt)\)，把这条边断开之后做树上问题，对于两个断开的点 \(lt,rt\) 分情况讨论。如果是只有一棵基环树可以使用并查集找环，如果是基环树森林可以先用并查集找出一个“有代表性的点”，然后再从这个点向上跳就可以找到 \(lt,rt\) 了。
回归到这道题。如何连边建立模型？如果我们用边 \((u,v)\) 表示 \(u\) 可以限制 \(v\)，我们会发现我们建立出来了若干棵内向基环树，不太好做。所以我们可以考虑用边 \((u,v)\) 表示 \(u\) 可以被 \(v\) 限制，即子节点可以限制父节点。
接着使用并查集来寻找这个有代表性的点。在输入的时候我们把 \(i,a_i\) 合并到一个集合中，然后在并查集的祖先数组 fa 数组中寻找，如果有结点的祖先是这个结点自己，那么就是一个“有代表性的点”，这个点代表着这个点所在的基环树。
对于基环树森林中的每一棵基环树，我们先从这个有代表性的点向上跳找环。开一个标记数组将当前点标记，如果下一个要跳到的点是有标记的，则说明找到环了，这个基环树中的 \(lt\) 是当前点，\(rt\) 是当前点所限制的元素。在建图的时候不建立 \((rt,lt)\) 这条边就好了。（注意顺序，我们边的定义是前者被后者限制）
对于样例数据，我们建立的图如下（被标记的点就是所找的有代表性的点）：
可以考虑 DP：设 \(dp_{u,0/1}\) 表示以 \(u\) 为根结点的子树，其中 \(u\) 不选 / 选的最大投放数量。我们将边 \((rt,lt)\) 删除建图之后，跑第一遍 DP。
对于第一遍 DP，考虑 \(u\) 结点如何转移？如果 \(u\) 结点没有放的话，那么它的儿子想怎么放都可以（因为子节点不要求限制父节点），于是我们有状态转移（其中 \(\operatorname{son}(u)\) 表示 \(u\) 结点所有儿子结点构成的集合）：
如果 \(u\) 选了怎么办？显然，我们只要让任意一个儿子结点限制 \(u\)，其他儿子结点任选即可。转移如下：
转移要枚举一个 \(v^\prime\)，太耗时间了，怎么办？发现 \(\sum_{v^\prime \operatorname{son}(u) ,v^\prime \neq v}\max\left\{dp_{v^\prime,0},dp_{v^\prime,1}\right\}\) 其实就是一个 \(dp_{u,0}\) 扣掉了一个 \(\max\left\{dp_{v,0},dp_{v,1}\right\}\)，于是转移可以优化成如下：
把 \(dp_{u,0}\) 拿出来：
这个就是我们最终的转移了。第一遍 DP 的答案就是 \(dp_{lt,0},dp_{lt,1}\) 取一个最大值。
第一遍 DP 我们删掉了 \((rt,lt)\) 这条边，强制让 \(lt\) 不能限制 \(rt\)。所以：
对于第二遍 DP，我们考虑强制让 \(lt\) 限制 \(rt\)，转移方程同第一遍 DP。但要注意的是因为我们强制让 \(lt\) 限制 \(rt\)，所以 \(rt\) 的儿子怎么选都没关系。对于 \(u=rt\) 的情况，\(dp_{u,1}\) 的转移变成如下：
考虑到我们强制让 \(lt\) 限制 \(rt\)，\(lt\) 一定不选，所以第二遍 DP 的答案就是 \(dp_{lt,0}\)。所以一棵基环树的贡献我们就算完了。有基环树森林的情况就直接一棵一棵算贡献，最后累加就好了。
参考程序：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e6+7;
int n,a[N];
bitset<N> vis;
vector<int> g[N];
vector<int> point; //有代表性的节点
namespace dsu
{int fa[N];void init(int n){for(int i=1;i<=n;i++) fa[i]=i;}int find(int u){return fa[u]==u?u:fa[u]=find(fa[u]); }void merge(int u,int v){fa[find(u)]=find(v);}bool judge(int u,int v) //u,v是否在一个连通块中 {return find(u)==find(v);}
}
constexpr int inf=12180211;
int ans=0,lt,rt;
int dp1[N][2],dp2[N][2];
void dfs1(int u)
{int mx=-121802110;for(int v:g[u]){if(v==lt) continue;dfs1(v);dp1[u][0]+=max(dp1[v][0],dp1[v][1]);mx=max(mx,dp1[v][0]-max(dp1[v][0],dp1[v][1]));}dp1[u][1]=1+dp1[u][0]+mx;
}
void dfs2(int u)
{int mx=-121802110;for(int v:g[u]){if(v==lt) continue;dfs2(v);dp2[u][0]+=max(dp2[v][0],dp2[v][1]);mx=max(mx,dp2[v][0]-max(dp2[v][0],dp2[v][1]));}if(u==rt) dp2[u][1]=1+dp2[u][0];else dp2[u][1]=1+dp2[u][0]+mx;
}inline int solve(int k)
{vis.reset();//寻找 lt,rt lt=-1,rt=-1;int cur=k; //当前点 vis[cur]=1;while(1){if(vis[a[cur]]) //向上跳发现有标记 那就说明找到环了 {lt=cur,rt=a[cur];break;}vis[a[cur]]=1;cur=a[cur];}//这里的lt,rt连边的方向是rt->lt //建图for(int i=1;i<=n;i++){int u=a[i],v=i;if(dsu::find(u)!=dsu::find(k)||dsu::find(v)!=dsu::find(k)) continue; //这一个solve只要考虑当前基环树的结果,不用考虑其他基环树if(!(u==rt&&v==lt)) g[u].push_back(v); //删掉的边(rt->lt)不连接 }//开始DPdfs1(lt);dfs2(lt);
// for(int i=1;i<=n;i++) cerr<<i<<' '<<dp1[i][0]<<' '<<dp1[i][1]<<' '<<dp2[i][0]<<' '<<dp2[i][1]<<endl;return max({dp1[lt][0],dp1[lt][1],dp2[lt][0]});
}
int main()
{
// freopen("neuvillette.in","r",stdin);
// freopen("neuvillette.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;dsu::init(n);for(int i=1;i<=n;i++){cin>>a[i];dsu::merge(a[i],i);}for(int i=1;i<=n;i++) if(dsu::fa[i]==i) point.push_back(i);for(int v:point){int res=solve(v);ans+=res;}cout<<ans;return 0;
}
/*
把a[i]->i连一条边,代表i可以被a[i]限制
用并查集把森林中的每一颗基环树都找出来
对于基环树森林中的每一颗基环树都考虑：
fa[i]=i就是一个“有代表性的”节点
首先先从每一个基环树这个有代表性的节点往上跳找环,
然后删掉环其中的一个边(lt,rt)然后开始DPdp[u][0/1]表示以u为根的子树且u不选/选的最大答案
根据连边的结果,节点u可以被u的所有儿子节点v限制
所以如果u选了就至少有一个v不选，如果u不选v选和不选都无所谓
dp[u][0]=∑max{dp[v][0],dp[v][1]}
dp[u][1]=1+max{dp[v][0]+∑max{dp[v'][0/1]}} 其中v'是u的儿子中除v以外的儿子,但是这个转移方程如果真的这么写肯定会超时的。怎么优化？
发现 ∑max{dp[v'][0/1]}就是dp[u][0]扣掉一个max{dp[v][0/1]}
然后方程可以优化成:
dp[u][1]=1+max{dp[v][0]+dp[u][0]-max{dp[v][0/1]}}
=1+dp[u][0]+max{dp[v][0]-max{dp[v][0/1]}}
然后以lt为根跑一遍DP
这样我们就得到了一个lt不能限制rt的方案dp1，答案为max{dp[lt][0/1]}
然后把这个删掉的边考虑上去，强制让lt限制住rt,也就是说这个lt只能不投放,就是dp[lt][0],然后这个lt的儿子节点都不受限制了
然后第二遍DP该怎么跑？
考虑到rt已经被限制了,所以他的儿子无论如何放都是合法的方案，所以第二次DP的状态转移方程就是：
对于u==rt(就是u被lt限制的情况)dp[u][1]=1+dp[u][0]
*/