6.2内训模拟赛题。
P10121 『STA - R4』保险丝
显然点越靠近点 u 越容易成为 u 的半邻域，越远离点 u 越不容易成为 u 的半邻域，所以点 u 的半邻域是一个连通块状。
需要一点注意力可以发现度数为 1 或 2 的点作为 v 时无贡献（Fibonacci 数列第一、二项都为 1），称度数 >= 2 的点为分叉点，进一步可以发现一个分叉点往上跳直到跳到上一个分叉点之前（类似于提取下面带分叉上为链状结构）作为 u 的贡献都是一样的，可以一起处理掉。
核心部分的计算流程是，
- 把树拍成 dfs 序列，子树编号连续
- 先算出半邻域的点数：\(x\) 的半邻域内点 \(y\) 满足 \(dep_y-dep_x \le dist_y\)，因此 \(dep_x \ge dep_y - dist_y\)，按 \(dep\) 分层后双指针。
- 求出每个点的半邻域中所有的分叉点
- 依次计算 \(f_i\)，在线段树上单点加上分叉点的贡献，区间查询贡献积。注意要按照从下到上的顺序加入线段树。
这么做时间正确的原因是，n 个点半领域和上界是 \(O(nlogn)\)，证明考虑构造一棵满二叉树，一个节点最多在 \(logn\) 个点的半邻域内。于是这样做就是 \(O(nlog^2n)\) 的，而且这是跑不满的所以可以过 1e6。略微卡常，洛谷上需要评测机波过去。为啥场上最优解是 \(O(n^2)\) 的，谴责赛时水水数据。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define lc rt * 2
#define rc rt * 2 + 1
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1000010;
const int p = 994007158;
int hed[N],nxt[N * 2],to[N * 2],n,tote,deg[N],totf,d[N],dep[N],fb[N],ans[N],tp[N];
int sta[N],tots,dfn[N],totn,sz[N],b[N],Tr[N],pt[N],tr[N * 4],faa[N];
vector<int> v[N],f[N];
void add(int &x,int y){x += y;if(x >= p)x -= p;}
void addedge(int x,int y){tote++,nxt[tote] = hed[x],to[tote] = y,hed[x] = tote;}
void dfs1(int x,int fa){d[x] = 1e9;dep[x] = dep[fa] + 1,faa[x] = fa;for(int i = hed[x]; i; i = nxt[i]){int y = to[i];if(y == fa)continue;dfs1(y,x);d[x] = min(d[x],d[y] + 1);}if(d[x] == 1e9)d[x] = 0;
}
void dfs2(int x,int fa){if(deg[x] > 2 || x == 1)tp[x] = sta[tots],sta[++tots] = x;dfn[x] = ++totn;sz[x] = 1;for(int i = hed[x]; i; i = nxt[i]){int y = to[i];if(y == fa)continue;d[y] = min(d[y],d[x]);dfs2(y,x);sz[x] += sz[y];}if(deg[x] > 2 || x == 1)tots--;
}
bool cmp(int x,int y){return dep[x] - d[x] < dep[y] - d[y];}
void addT(int x,int y){x++;for(; x <= n + 1; x += (x & -x))Tr[x] += y;}
int sumT(int x){x++;int res = 0;for(; x; x -= (x & -x)){res += Tr[x];}return res;}
void build(int rt,int l,int r){tr[rt] = 1;if(l == r){return;}build(lc,l,mid);build(rc,mid + 1,r);
}
void modify(int rt,int l,int r,int x,int y){if(l == r){tr[rt] = y;return;}if(mid >= x)modify(lc,l,mid,x,y);else modify(rc,mid + 1,r,x,y);tr[rt] = tr[lc] * tr[rc] % p;
}
int query(int rt,int l,int r,int x,int y){if(l >= x && r <= y)return tr[rt];int res = 1;if(mid >= x)res = res * query(lc,l,mid,x,y) % p;if(mid + 1 <= y)res = res * query(rc,mid + 1,r,x,y) % p;return res;
}
signed main(){//freopen("fuse.in","r",stdin);//freopen("fuse.out","w",stdout);scanf("%lld",&n);fb[1] = fb[2] = 1;for(int i = 3; i <= n; i++)fb[i] = (fb[i - 1] + fb[i - 2]) % p;for(int i = 2,x; i <= n; i++)scanf("%lld",&x),addedge(i,x),addedge(x,i),deg[i]++,deg[x]++;dfs1(1,0);dfs2(1,0);for(int i = 1; i <= n; i++)b[i] = i,v[dep[i]].push_back(i);sort(b + 1,b + n + 1,cmp);for(int i = 1,j = 0; i <= n; i++){while(j < n && dep[b[j + 1]] - i <= d[b[j + 1]])addT(dfn[b[++j]],1);for(int j = 0; j < v[i].size(); j++){pt[v[i][j]] = sumT(dfn[v[i][j]] + sz[v[i][j]] - 1) - sumT(dfn[v[i][j]] - 1);}}for(int i = n; i >= 1; i--){int x = b[i];if(x != 1 && deg[x] <= 2)continue;for(int j = x; j && dep[x] - dep[j] <= d[x]; j = faa[j])f[j].push_back(x);}build(1,1,n);for(int i = 1; i <= n; i++){for(int j = 0; j < f[i].size(); j++){int x = f[i][j];modify(1,1,n,dfn[x],fb[deg[x]]);add(ans[i],query(1,1,n,dfn[x],dfn[x] + sz[x] - 1) * (dep[x] - max(dep[tp[x]],dep[i] - 1)) % p);pt[i] -= dep[x] - max(dep[tp[x]],dep[i] - 1);}add(ans[i],pt[i]);for(int j = 0; j < f[i].size(); j++)modify(1,1,n,dfn[f[i][j]],0);}int Ans = 0;for(int i = 1; i <= n; i++)Ans ^= ans[i];printf("%lld",Ans);return 0;
}