[洛谷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<cstdio>

#include<cctype>

#include<vector>

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<int> 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<n;i++) {

		add_edge(getint(),getint());

	}

	dfs(1,0);

	printf("%lld\n",ans);

	return 0;

}