fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll int64_t
  3. #define ld long double
  4. using namespace std;
  5. // 
  6. const int maxn =1e6+5;
  7. const int mod = 1e9+7; // 998244353,1610612741
  8. const ll inf = 1e18;
  9. const ld pi = atan(1.0L)*4;
  10. int n,curc,curp,chd[maxn],cid[maxn],par[maxn],sz[maxn],pos[maxn],a[maxn],mn[maxn],mx[maxn],h[maxn],l[maxn],r[maxn];
  11. vector<int> g[maxn];
  12. pair<int,int> st[20][maxn];
  13. void build(){
  14.    int k=__lg(n);
  15.    for (int i=1;i<=n;i++) st[0][i]={a[i],a[i]};
  16.    for (int j=1;j<=k;j++){
  17.       for (int i=1;i+(1<<j)-1<=n;i++)  
  18.       	st[j][i]={min(st[j-1][i].first,st[j-1][i+(1<<(j-1))].first),
  19. 						 max(st[j-1][i].second,st[j-1][i+(1<<(j-1))].second)};
  20.    }
  21. }
  22. pair<int,int> get(int l,int r){
  23.    int k=__lg(r-l+1);
  24.    return {min(st[k][l].first,st[k][r-(1<<k)+1].first),
  25.    		  max(st[k][l].second,st[k][r-(1<<k)+1].second)};
  26. }
  27. void dfs(int u,int p=-1) {
  28. 	sz[u]=1;
  29. 	for (auto v:g[u]){
  30. 		if (v!=p) {
  31. 			par[v]=u;
  32. 			h[v]=h[u]+1;
  33. 			dfs(v,u);
  34. 			sz[u]+=sz[v];
  35. 		}
  36. 	} 
  37. }
  38. void hld(int u,int p=-1) {
  39. 	if (!chd[curc]) chd[curc]=u;
  40. 	cid[u]=curc;
  41. 	pos[u]=curp;
  42. 	a[curp++]=u;
  43. 	int mx=0;
  44. 	for (auto v:g[u]) {
  45. 		if (v!=p&&sz[mx]<sz[v]) mx=v;
  46. 	}
  47. 	if (mx) hld(mx,u);
  48. 	for (auto v:g[u]) {
  49. 		if (v!=p&&v!=mx) curc++,hld(v,u);
  50. 	}
  51. }
  52. int lca(int u,int v) {
  53.     while (cid[u]^cid[v]) {
  54.         if (cid[u]>cid[v]) u=par[chd[cid[u]]];
  55.         else v=par[chd[cid[v]]];
  56.     }
  57.     return (h[u]<h[v]?u:v);
  58. }
  59. pair<int,int> query(int u,int v){
  60. 	int p =lca(u,v);
  61. 	pair<int,int> res={mod,0};
  62. 	while (cid[u]!=cid[p]) {
  63. 		auto x=get(pos[chd[cid[u]]],pos[u]);
  64. 		res={min(res.first,x.first),max(res.second,x.second)};
  65. 		u=par[chd[cid[u]]];
  66. 	}
  67. 	while (cid[v]!=cid[p]) {
  68. 		auto x=get(pos[chd[cid[v]]],pos[v]);
  69. 		res={min(res.first,x.first),max(res.second,x.second)};
  70. 		v=par[chd[cid[v]]];
  71. 	}
  72. 	if (h[u]<h[v]) {
  73. 		auto x=get(pos[u],pos[v]);
  74. 		res={min(res.first,x.first),max(res.second,x.second)};
  75. 	}
  76. 	else {
  77. 		auto x=get(pos[v],pos[u]);
  78. 		res={min(res.first,x.first),max(res.second,x.second)};
  79. 	}
  80. 	return res;
  81. }
  82. pair<int,int> t[20][maxn];
  83. void build2(){
  84.    int k=__lg(n);
  85.    for (int i=1;i<=n;i++) t[0][i]={mn[i],mx[i]};
  86.    for (int j=1;j<=k;j++){
  87.       for (int i=1;i+(1<<j)-1<=n;i++)  
  88.       	t[j][i].first=min(t[j-1][i].first,t[j-1][i+(1<<(j-1))].first),
  89. 			t[j][i].second=max(t[j-1][i].second,t[j-1][i+(1<<(j-1))].second);
  90.    }
  91. }
  92. pair<int,int> get2(int l,int r){
  93.    int k=__lg(r-l+1);
  94.    return {min(t[k][l].first,t[k][r-(1<<k)+1].first),
  95.    		  max(t[k][l].second,t[k][r-(1<<k)+1].second)};
  96. }
  97. struct nai{
  98. 	int l,r,val,tp,id;
  99. };
  100. int bit[maxn*2];
  101. nai A[maxn*2];
  102. void update(int i) {
  103. 	for (;i<=n+6942;i+=i&-i) bit[i]++;
  104. }
  105. int query(int i){
  106. 	int res=0;
  107. 	for (;i>0;i-=i&-i) res+=bit[i];
  108. 	return res;
  109. }
  110. int main() {
  111. //   freopen("../input.inp","r",stdin);
  112. //   freopen("output.out","w",stdout);
  113.    ios::sync_with_stdio(false);
  114.    cin.tie(nullptr);
  115.    cin >>n;
  116.    for (int i=1;i<n;i++) {
  117.    	int u,v;
  118.    	cin >>u>>v;
  119.    	g[u].push_back(v);
  120.   		g[v].push_back(u);
  121.    }
  122.    curc=curp=1;
  123.    dfs(1);hld(1);
  124.    build();
  125.    for (int i=1;i<n;i++) {
  126.    	auto p=query(i,i+1);
  127.    	mn[i]=p.first,mx[i]=p.second;
  128.    }
  129.    ll res=n;
  130.    build2();
  131.    for (int i=1;i<n;i++) {
  132.    	if (mn[i]<i) {
  133.    		r[i]=i;
  134.    		continue;
  135.    	}
  136.    	int L=i,R=n;
  137.    	while (L<=R) {
  138.    		int mid =(L+R)/2;
  139.    		if (get2(i,mid).first>=i) L=mid+1;
  140.    		else R=mid-1;
  141.    	}
  142.    	r[i]=L;
  143.    }
  144.    for (int i=2;i<=n;i++) {
  145.    	if (mx[i-1]>i) {
  146.    		l[i]=i;
  147.    		continue;
  148.    	}
  149.    	int L=1,R=i-1;
  150.    	while (L<=R){
  151.    		int mid =(L+R)/2;
  152.    		if (get2(mid,i-1).second<=i) R=mid-1;
  153.    		else L=mid+1;
  154.    	}
  155.    	l[i]=R;
  156.    }
  157.    for (int i=1;i<=n;i++) {
  158. 		A[i].val=l[i];
  159.    	A[i].l=A[i].r=i;
  160.    	A[i].tp=-1;
  161.    }
  162.    int q=0;
  163.   	for (int i=1;i<n;i++) {
  164.    	if (r[i]+1>=i) {
  165.    		q++;
  166.    		A[q+n].l=i+1;
  167.    		A[q+n].r=r[i];
  168.    		A[q+n].val=i-1;
  169.    	}
  170.    }
  171.    sort(A+1,A+1+q+n,[&](nai x,nai y) {return x.val>y.val||(x.val==y.val&&x.tp>y.tp);});
  172.    for (int i=1;i<=n+q;i++) {
  173.    	if (A[i].tp==-1) update(A[i].l);
  174.    	else res+=1ll*A[i].r-A[i].l+1-query(A[i].r)+query(A[i].l-1);
  175.    }
  176.    cout<<res;
  177.    return 0;
  178. }
Success #stdin #stdout 0.01s 38300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GizYa3
language:
C++ (gcc 8.3)
created:
362 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!