首先有一个比较显然的 $60pts$ 做法，考虑枚举区间的左端点，然后以它为根，把每个节点的父亲记录下来，然后我枚举右端点，并且从它开始往上跳父亲，跳到的点打一个标记，如果跳到了标记过的点就停止，并且记录路径长度。

这样做为什么是对的？首先我每个点最多遍历一次，复杂度有保证，然后往上跳的过程可以看做是增广之前的生成树，因为要边数最小，我增广的必然是一条路径，然后就可以愉快地获得 $60pts$ 。

CODE

#include<bits/stdc++.h>
using namespace std;
vector<int>G[100005];
int f[100005];
bool vis[100005];
void dfs(int x,int fa){
	for(int i=0; i<G[x].size(); i++){
		int y=G[x][i];
		if(y==fa)continue;
		dfs(y,f[y]=x);
	}
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1; i<n; i++){
		int x,y;scanf("%d%d",&x,&y);
		G[x].push_back(y),G[y].push_back(x);
	}long long ans=0;
	for(int i=1; i<=n; i++){
		f[i]=i;memset(vis,0,sizeof vis);
		dfs(i,i);
		for(int j=i; j<=n; j++){
			int t=j,cnt=0;
			while(!vis[t])vis[t]=1,t=f[t],cnt++;
			if(i==j)cnt=0;
			ans+=cnt*1ll*(n-j+1);
		}
	}cout<<ans;
	return 0;
}

然后正解做法和这个完全没有关系。。。。（那你写上面干什么）

我们沿用上面增广的思路是困难的，（因为我想了两个小时也不会） 因为我们要维护的是一个后缀的树，每个点插入到后缀的树当中，总之比较难搞。不过我发现了一个疑似正确的性质，就是说不管以哪个点为根，一个点的增广路径一定都在它到它的编号的前一个节点的路径上。可能沿着这条性质会有另外一种做法，但是我也不太会。

下面我来说我的正解做法。不放可以换一个角度做统计，考虑我们对每条边做统计，计算经过它的树有多少。我们不难发现，每一条边对应一棵子树，显然，经过它的树必然是那些区间的一部分点在子树内，一部分点在子树外的。而这个子树当中出现的节点可以用一个 $0/1$ 序列来表示每个节点是否存在。那么我们的问题等价为对于每一个子树，统计它对应的 $01$ 序列不只包含一种数的区间个数。正难则反，我们可以统计只包含 $0$ 或 $1$ 的个数。

我们考虑用线段树来维护，线段树上记录一下答案, $l0$ , $r0$, $l1$ , $r1$。其中 $l0$ 表示该区间内连续的极长前缀 $0$ 的个数，$r0$ 表示极长后缀 $0$ 的个数，另外两个同理。我们对于每一个子树都这样维护，并且在统计后把当前线段树合并到上面就好了。

$pushup$ 中的细节比较多，具体参照代码：

#include<bits/stdc++.h>
#define lson tr[rt].ls
#define rson tr[rt].rs
using namespace std;
vector<int>G[100005];
struct node{
	int ls,rs;
	int l0,r0,l1,r1;
	long long sum;
}tr[5000005];
int T[100005],siz[100005];
int tot;
bool debug;
inline int newnode(int lenth){
	int rt=++tot;
	tr[rt].l0=tr[rt].r0=lenth;
	tr[rt].l1=tr[rt].r1=0;
	tr[rt].sum=(lenth)*1ll*(lenth+1)/2;
	return rt;
}



// 关注这个函数
inline void pushup(int rt,int l,int r){
	int mid=l+r>>1;
	if(!lson)lson=newnode(mid-l+1);
	if(!rson)rson=newnode(r-mid);
	tr[rt].sum=tr[lson].sum+tr[rson].sum;
	tr[rt].l0=tr[lson].l0,tr[rt].l1=tr[lson].l1;
	tr[rt].r0=tr[rson].r0,tr[rt].r1=tr[rson].r1;
	if(tr[lson].l0==mid-l+1)tr[rt].l0+=tr[rson].l0;
	if(tr[rson].r0==r-mid)tr[rt].r0+=tr[lson].r0;
	if(tr[lson].l1==mid-l+1)tr[rt].l1+=tr[rson].l1;
	if(tr[rson].r1==r-mid)tr[rt].r1+=tr[lson].r1;
	long long cnt0=tr[lson].r0*1ll*tr[rson].l0,cnt1=tr[lson].r1*1ll*tr[rson].l1;
	tr[rt].sum+=cnt0+cnt1;
}




int update(int rt,int l,int r,int x){
	if(!rt){
		rt=newnode(r-l+1);
	}
	if(l==r){
		tr[rt].l0=tr[rt].r0=0;
		tr[rt].l1=tr[rt].r1=1;
		tr[rt].sum=1;
		return rt;
	}int mid=l+r>>1;
	if(x<=mid)lson=update(lson,l,mid,x);
	else rson=update(rson,mid+1,r,x);
	pushup(rt,l,r);
	return rt;
}int merge(int x,int y,int l,int r){
	if(!x||!y)return x|y;
	if(l==r){
		if(tr[y].l1){
			tr[x].l1=tr[x].r1=1;
			tr[x].l0=tr[x].r0=0;
			tr[x].sum=1;
		}return x;
	}int mid=l+r>>1;
	tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);
	tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
	pushup(x,l,r);
	return x;
}int n;
long long ans=0;
void dfs(int x,int fa){
	debug=(x==7);
	T[x]=update(T[x],1,n,x);
	siz[x]=1;
	for(int i=0; i<G[x].size(); i++){
		int y=G[x][i];
		if(y==fa)continue;
		dfs(y,x);
		siz[x]+=siz[y];
		ans+=n*1ll*(n+1)/2-tr[T[y]].sum;
		debug=(x==7);
		T[x]=merge(T[x],T[y],1,n);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1; i<n; i++){
		int x,y;scanf("%d%d",&x,&y);
		G[x].push_back(y),G[y].push_back(x);
	}
	dfs(1,1);
	cout<<ans;
	return 0;
} /*
9
1 2
1 3
3 4
3 6
2 5
2 9
9 7
9 8

*/