又是爆零的一天！
没写出的题就写写知识点吧：
-
T1:线段树合并
-
T3:kruskal重构树
-
T4:FFT
T2
题目大意：一棵树，对于每一个(i)，求有多少个(j)为(i)的联系节点，(j)满足(forall k(j<kle i))都是(j)的子孙节点。
题目挺简单，但考场上完全想错方向，对于(j)的右边最多可以作为那些(i)的联系节点，易证这些(i)一定是连续的，而且紧挨着(j)，因为一旦有一个不是(j)的子孙节点，后面的就都不会是(j)的联系节点了。所以我们就可以二分这个右端点，用(dfs)序或许是一个不错的选择。
众所周知，只要(i)满足(dfn_jle dfn_ile dfn_j+size_j-1)，(i)就在(j)的子树内，所以用(st)表维护一个(dfn)的最大值和最小值，卡卡常就可以(O(nlogn))解决此题。
#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=2200005;
inline int read()
{
re int x=0,f=1;
re char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') f*=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
void print(int x)
{
if(x>9) print(x/10);
putchar(x%10^48);
}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
struct edge{int v,net;}e[N];
int n,cnt,hd[N],dfn[N],siz[N],tot,mi[N][22],ma[N][22],sum[N];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].net=hd[u],hd[u]=cnt;}
void first(int u)
{
dfn[u]=++tot,siz[u]=1;
for(re int i=hd[u],v;i;i=e[i].net)
{
v=e[i].v;
first(v);
siz[u]+=siz[v];
}
return ;
}
int main()
{
freopen("ancestor.in","r",stdin);
freopen("ancestor.out","w",stdout);
n=read();
for(re int i=2;i<=n;i++) add(read(),i);
first(1),ma[n][0]=mi[n][0]=dfn[n];
for(re int i=n-1;i>0;i--)
{
mi[i][0]=min(dfn[i],dfn[i+1]);
ma[i][0]=max(dfn[i],dfn[i+1]);
for(re int j=1;j<22;j++)
{
if(i+(1<<j)>n) break;
mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
ma[i][j]=max(ma[i][j-1],ma[i+(1<<j-1)][j-1]);
}
}
for(re int i=1,mid;i<=n;i++)
{
mid=i;
for(re int j=21;j>=0;j--)
if(mid+(1<<j)<=n&&ma[mid][j]<=dfn[i]+siz[i]-1&&mi[mid][j]>=dfn[i]) mid=mid+(1<<j);
sum[i]++,sum[mid+1]--;
}
for(re int i=1;i<=n;i++) sum[i]+=sum[i-1];
for(re int i=1;i<=n;i++) print(sum[i]),putchar('
');
return 0;
}