[nowcoder5669A]Ancient Distance

对于一个$k$，可以二分枚举答案并判断，判断过程可以贪心找最深的点（线段树区间max）+倍增+线段树区间覆盖（清0）来实现，时间复杂度$o(klog_{2}n)$

考虑反过来，暴力枚举答案$x$并求出最少需要的点数量$f(x)=k$，那么$\forall \ f(x)\le i< f(x-1)$，都有$i$的答案为$x$

这样的复杂度看似仍然是$o(n^{2}log_{2}n)$，但发现一次贪心至少覆盖$x+1$个点或者已经是最后一次，也就是说最多说单次复杂度为$o(\lceil \frac{n}{x+1}\rceil log_{2}n)$，累加后通过调和级数保证复杂度为$o(nlog^{\ 2
}_{2}n)$

具体线段树的实现上可能比较难，可以再维护一个$tag[k]$表示，可能标记永久化+重新修改来实现会比较方便

另外常数较大，注意线段树常数

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define L (k<<1)

 5 #define R (L+1)

 6 #define mid (l+r>>1)

 7 struct ji{

 8     int nex,to;

 9 }edge[N];

10 vector<int>v;

11 int E,n,x,head[N],dfn[N],sz[N],sh[N],tr[N<<2],tr2[N<<2],tag[N<<2],f[N][21];

12 void add(int x,int y){

13     edge[E].nex=head[x];

14     edge[E].to=y;

15     head[x]=E++;

16 }

17 void build(int k,int l,int r){

18     tag[k]=1;

19     if (l==r){

20         tr[k]=tr2[k]=sh[l];

21         return;

22     }

23     build(L,l,mid);

24     build(R,mid+1,r);

25     tr[k]=tr2[k]=max(tr[L],tr[R]);

26 }

27 void update(int k,int l,int r,int x,int y,int z){

28     if ((l>y)||(x>r))return;

29     if ((x<=l)&&(r<=y)){

30         tag[k]=z;

31         tr[k]=tr2[k]*z;

32         return;

33     }

34     update(L,l,mid,x,y,z);

35     update(R,mid+1,r,x,y,z);

36     tr[k]=max(tr[L],tr[R])*tag[k];

37 }

38 int query(int k,int l,int r){

39     if (l==r)return l;

40     if (tr[k]==tr[L])return query(L,l,mid);

41     return query(R,mid+1,r);

42 }

43 void dfs(int k,int fa,int s){

44     sz[k]=1;

45     sh[k]=s;

46     dfn[k]=++x;

47     f[k][0]=fa;

48     for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1];

49     for(int i=head[k];i!=-1;i=edge[i].nex){

50         dfs(edge[i].to,k,s+1);

51         sz[k]+=sz[edge[i].to];

52     }

53 }

54 int find(int k,int x){

55     for(int i=0;i<=20;i++)

56         if (x&(1<<i))k=f[k][i];

57     return k;

58 }

59 int main(){

60     while (scanf("%d",&n)!=EOF){

61         E=0;

62         for(int i=1;i<=n;i++)head[i]=-1;

63         for(int i=2;i<=n;i++){

64             scanf("%d",&x);

65             add(x,i);

66         }

67         x=0;

68         dfs(1,1,1);

69         build(1,1,n);

70         int ans=-1;

71         for(int i=1;i<=n;i++){

72             v.clear();

73             while (1){

74                 x=find(query(1,1,n),i);

75                 if (x==1)break;

76                 v.push_back(x);

77                 update(1,1,n,dfn[x],dfn[x]+sz[x]-1,0);

78             }

79             for(int j=0;j<v.size();j++)update(1,1,n,dfn[v[j]],dfn[v[j]]+sz[v[j]]-1,1);

80             ans+=v.size()+1;

81         }

82         printf("%d\n",ans);

83     }

84 }

巴特西

[nowcoder5669A]Ancient Distance

最新文章

热门文章