竟然作死 lower_bound(s[u].begin(),s[u].end(),*it1); T的不明所以QAQ
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<set> #include<time.h> using namespace std; const int MAXN=(int)1e5+10; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } typedef long long ll; struct edge{ int to,nxt; }ed[MAXN<<1]; int head[MAXN],cnt; void addedge(int u,int v){ ed[cnt].to=v; ed[cnt].nxt=head[u]; head[u]=cnt++; } struct node{ int l,r; node(){}node(int _l,int _r){l=_l;r=_r;} bool operator < (const node &a)const{ if(l==a.l)return r<a.r; else return l<a.l; } }; set<node>s[MAXN]; set<node>::iterator it1,it2,it3; int idx[MAXN]; ll vl[MAXN],ans;int n; ll gx(ll x){return x*(x-1)/2;} void merge(int &u,int &v){ if(s[u].size()<s[v].size())swap(u,v); for(it1=s[v].begin();it1!=s[v].end();it1++){ it2=s[u].lower_bound(*it1); if(it2==s[u].end()){ while(it1!=s[v].end()){ it2=s[u].end(); it2--; if(it1->l==it2->r+1){ vl[u]-=gx(n-it2->r); vl[u]-=gx(it2->r-it2->l+1); vl[u]+=gx(it1->r-it2->l+1); vl[u]+=gx(n-it1->r); node nw=node(it2->l,it1->r); s[u].erase(it2); s[u].insert(nw); } else { vl[u]-=gx(n-it2->r); vl[u]+=gx(it1->l-it2->r-1); vl[u]+=gx(it1->r-it1->l+1); vl[u]+=gx(n-it1->r); s[u].insert(*it1); } it1++; } break; } else if(it2==s[u].begin()){ if(it1->r+1==it2->l){ vl[u]-=gx(it2->r-it2->l+1); vl[u]-=gx(it2->l-1); vl[u]+=gx(it1->l-1); vl[u]+=gx(it2->r-it1->l+1); node nw=node(it1->l,it2->r); s[u].erase(it2); s[u].insert(nw); } else { vl[u]-=gx(it2->l-1); vl[u]+=gx(it1->l-1); vl[u]+=gx(it1->r-it1->l+1); vl[u]+=gx(it2->l-it1->r-1); s[u].insert(*it1); } } else { it3=it2;it3--; if(it3->r+1==it1->l&&it1->r+1==it2->l){ vl[u]-=gx(it2->r-it2->l+1)+gx(it3->r-it3->l+1)+gx(it1->r-it1->l+1); vl[u]+=gx(it2->r-it3->l+1); node nw=node(it3->l,it2->r); s[u].erase(it2); s[u].erase(it3); s[u].insert(nw); } else if(it3->r+1==it1->l){ vl[u]-=gx(it2->l-it3->r-1); vl[u]-=gx(it3->r-it3->l+1); vl[u]+=gx(it1->r-it3->l+1); vl[u]+=gx(it2->l-it1->r-1); node nw=node(it3->l,it1->r); s[u].erase(it3); s[u].insert(nw); } else if(it1->r+1==it2->l){ vl[u]-=gx(it2->l-it3->r-1); vl[u]-=gx(it2->r-it2->l+1); vl[u]+=gx(it1->l-it3->r-1); vl[u]+=gx(it2->r-it1->l+1); node nw=node(it1->l,it2->r); s[u].erase(it2); s[u].insert(nw); } else { vl[u]-=gx(it2->l-it3->r-1); vl[u]+=gx(it1->l-it3->r-1)+gx(it1->r-it1->l+1)+gx(it2->l-it1->r-1); s[u].insert(*it1); } } } } void dfs(int u,int pre){ s[idx[u]].insert(node(u,u)); vl[u]=gx(u-1)+gx(n-u); for(int i=head[u];i!=-1;i=ed[i].nxt){ int v=ed[i].to; if(v!=pre){ dfs(v,u); ans-=vl[idx[v]]; merge(idx[u],idx[v]); } } } int main() { memset(head,-1,sizeof(head)); n=read(); for(int i=1;i<=n;i++)idx[i]=i; for(int i=1;i<n;i++){ int u,v; u=read();v=read(); addedge(u,v); addedge(v,u); } ans=1LL*n*(n-1)/2*(n-1); dfs(n/2+1,0); printf("%lld\n",ans); return 0; }