题目

有一棵 \(n\) 个结点的树，按顺序给出树边 \((fa[i],i)\)，

\(Q\) 次询问查询如果只选取第 \([l,r]\) 条树边，问森林的直径

\(fa[i]\) 的生成方式为 \(fa[i]=rand()\bmod{i-1}+1\)

\(n,Q\leq 5*10^5\)

分析

先不考虑树的具体形态，就求直径而言，答案会存放在父节点，

由于边的顺序是按子节点升序排列，那么固定左端点 \(l\)，根节点只会增加不会减少，

按照 \(l\) 降序排序，就要令 \(r\) 尽量小，设 \(f[x][d]\) 表示以 \(x\) 为根的子树内到一点距离 \(d\) 时 \(r\) 的最小值，

\(dp[d]\) 表示两点直径为 \(d\) 时 \(r\) 的最小值，就先用 \(f[x]\) 和 \(f[y]\) 更新 \(dp\)，再更新 \(f[x]\)。

时间复杂度取决于直径的长度，即 \(O(qd^2)\)

从没有想到这种 \(fa[i]\) 的生成会令树高期望为 \(O(\log{n})\)，那么时间复杂度为 \(O(q\log^2{n})\)，两个 \(\log\) 两秒肯定跑得完。

大概证明一下，设 \(dp[i]\) 表示第 \(i\) 个点的期望深度 \(dp[1]=0\)，那么 \(dp[i]=\frac{1}{i-1}\sum_{j=1}^{i-1}dp[j]+1\Rightarrow (i-1)dp[i]=S[i-1]+(i-1)\)

那么 \(dp[i-1]=\frac{1}{i-2}\sum_{j=1}^{i-2}dp[j]+1\Rightarrow (i-2)dp[i-1]=S[i-2]+(i-2)\)

两式相减就可以得到 \(dp[i]=dp[i-1]+\frac{1}{i-1}\)，因为 \(\sum_{i=1}^n\frac{1}{i}\) 趋近于 \(\log\)，

所以期望高度就是 \(\log{n}\)，但实际上高度在两倍左右

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=500011,mx=40; struct rec{int l,r;}q[N];
int dp[81],f[N][41],n,m,fa[N]; long long ans;
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
bool cmp(rec x,rec y){
    if (x.l!=y.l) return x.l>y.l;
        else return x.r>y.r;
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a1&&q[l].l<=j;--j) update(fa[j],j);
		for (int i=l,j=mx*2;i<=r;++i){
			while (dp[j]>q[i].r) --j;
		    ans+=j;
		}
	}
	return !printf("%lld",ans);
}