[洛谷U40581]树上统计treecnt
题目大意：
给定一棵\(n(n\le10^5)\)个点的树。
定义\(Tree[l,r]\)表示为了使得\(l\sim r\)号点两两连通，最少需要选择的边的数量。
求\(\sum_{l=1}^n\sum_{r=l}^nTree[l,r]\)。
思路：
对于每个边考虑贡献，若我们将出现在子树内的点记作\(1\)，出现在子树外的点记作\(0\)，那么答案就是\(\frac{n(n-1)}2-\)全\(0\)、全\(1\)串的个数。线段树合并，维护前缀/后缀最长全\(0\)/全\(1\)串即可。
时间复杂度\(\mathcal O(n\log n)\)。
源代码：
#include#include #include inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x;}typedef long long int64;const int N=1e5+1,logN=18;int n;int64 ans;std::vector e[N];inline void add_edge(const int &u,const int &v) { e[u].push_back(v); e[v].push_back(u);}inline int64 calc(const int &n) { return 1ll*n*(n-1)/2;}struct Node { int pre[2],suf[2],len; int64 sum; Node() {} Node(const int &l,const bool &v) { pre[!v]=suf[!v]=0; pre[v]=suf[v]=len=l; sum=calc(l); } friend Node operator + (const Node &l,const Node &r) { Node ret; ret.pre[0]=l.pre[0]+r.pre[0]*(l.pre[0]==l.len); ret.pre[1]=l.pre[1]+r.pre[1]*(l.pre[1]==l.len); ret.suf[0]=r.suf[0]+l.suf[0]*(r.suf[0]==r.len); ret.suf[1]=r.suf[1]+l.suf[1]*(r.suf[1]==r.len); ret.len=l.len+r.len; ret.sum=l.sum+r.sum+1ll*l.suf[0]*r.pre[0]+1ll*l.suf[1]*r.pre[1]; return ret; }};class SegmentTree { #define mid ((b+e)>>1) private: Node node[N*logN]; int left[N*logN],right[N*logN]; int sz,new_node() { return ++sz; } int len(const int &b,const int &e) { return e-b+1; } void push_up(const int &p,const int &b,const int &e) { if(!left[p]) node[p]=Node(len(b,mid),0)+node[right[p]]; if(!right[p]) node[p]=node[left[p]]+Node(len(mid+1,e),0); if(left[p]&&right[p]) { node[p]=node[left[p]]+node[right[p]]; } } public: int root[N]; void insert(int &p,const int &b,const int &e,const int &x) { if(!p) p=new_node(); if(b==e) { node[p]=Node(1,1); return; } if(x<=mid) insert(left[p],b,mid,x); if(x>mid) insert(right[p],mid+1,e,x); push_up(p,b,e); } void merge(int &p,const int &q,const int &b,const int &e) { if(!p||!q) { p=p|q; return; } if(b==e) return; merge(left[p],left[q],b,mid); merge(right[p],right[q],mid+1,e); push_up(p,b,e); } int64 query(const int &p) const { return node[p].sum; } #undef mid};SegmentTree t;void dfs(const int &x,const int &par) { t.insert(t.root[x],1,n,x); for(auto &y:e[x]) { if(y==par) continue; dfs(y,x); t.merge(t.root[x],t.root[y],1,n); } if(x!=1) ans-=t.query(t.root[x]);}int main() { n=getint(); ans=calc(n)*(n-1); for(register int i=1;i