[ZJOI2019]语言
法一： O(nlog^3)树剖+矩形面积并
法二：O(nlog^2)
一个点能到达的点是所有经过它的链的链并的大小
给出m个链求链并：
类似虚树
dfn序排序，ans+=dep[mem[i]]-dep[lca(mem[i],mem[i-1])]
每个边一定会统计到。
维护？
每个链树剖拆成logn份，线段树分治+线段树
下标都是dfn序
dfn相邻的贡献答案
法三：O(nlogn)
不再从dfn序列孤立地考虑树链
从树上直接考虑
经过一个点x的链一定一端在x的子树，启发我们线段树合并！
下标还是dfn序
树上差分打标记，8个标记。
lca可以O(1)求
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{ const int N=1e5+5; int n,m; struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } int dfn[N],df,fdfn[N]; int st[N],num; int dep[N]; int mem[2*N]; int fa[N]; void dfs(int x,int d){ dep[x]=d;dfn[x]=++df; fdfn[df]=x; st[x]=++num;mem[num]=x; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x]) continue; fa[y]=x; dfs(y,d+1); mem[++num]=x; } } int anc[2*N][20]; int lg[2*N]; int lca(int x,int y){ if(!x||!y) return 0; if(st[x]>st[y]) swap(x,y); x=st[x],y=st[y]; int len=lg[y-x+1]; int p1=anc[x][len],p2=anc[y-(1<<len)+1][len]; return dep[p1]<dep[p2]?p1:p2; } int con(int x,int y){ if(!x||!y) return 0; return dep[fdfn[y]]-dep[lca(fdfn[x],fdfn[y])]; } struct tr{ int ls,rs; int le,ri; int tag; int ans; }t[N*160]; #define mid ((l+r)>>1) int tot; void pushup(int x){ t[x].ans=t[t[x].ls].ans+t[t[x].rs].ans+con(t[t[x].ls].ri,t[t[x].rs].le); t[x].ri=t[t[x].rs].ri?t[t[x].rs].ri:t[t[x].ls].ri; t[x].le=t[t[x].ls].le?t[t[x].ls].le:t[t[x].rs].le; } int rt[N]; void upda(int &x,int l,int r,int p,int c){ if(!x) x=++tot; if(l==r){ t[x].tag+=c; if(t[x].tag>0) t[x].le=t[x].ri=l; else t[x].le=t[x].ri=0; return; } if(p<=mid) upda(t[x].ls,l,mid,p,c); else upda(t[x].rs,mid+1,r,p,c); pushup(x); } int merge(int x,int y,int l,int r){ if(!x||!y) return x+y; if(l==r){ t[x].tag+=t[y].tag; if(t[x].tag>0) t[x].le=t[x].ri=l; else t[x].le=t[x].ri=0; return x; } t[x].ls=merge(t[x].ls,t[y].ls,l,mid); t[x].rs=merge(t[x].rs,t[y].rs,mid+1,r); pushup(x); return x; } ll ans; void sol(int x){ for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x]) continue; sol(y); rt[x]=merge(rt[x],rt[y],1,n); } int now=t[rt[x]].ans+dep[fdfn[t[rt[x]].le]]-dep[fa[lca(fdfn[t[rt[x]].le],fdfn[t[rt[x]].ri])]]; // cout<<" sol "<<x<<" now "<<now<<" ans "<<t[rt[x]].ans<<" "<<endl; if(now) ans+=now-1; } int main(){ rd(n);rd(m); int x,y; for(reg i=1;i<n;++i){ rd(x);rd(y); add(x,y);add(y,x); } dfs(1,1); for(reg i=1;i<=num;++i) { anc[i][0]=mem[i]; lg[i]=(i>>(lg[i-1]+1)?lg[i-1]+1:lg[i-1]); } for(reg j=1;j<=17;++j){ for(reg i=1;i+(1<<j)-1<=num;++i){ anc[i][j]=dep[anc[i][j-1]]<dep[anc[i+(1<<(j-1))][j-1]]?anc[i][j-1]:anc[i+(1<<(j-1))][j-1]; } } for(reg i=1;i<=m;++i){ rd(x);rd(y); int z=lca(x,y); // cout<<" zz "<<z<<endl; upda(rt[x],1,n,dfn[x],1); upda(rt[x],1,n,dfn[y],1); upda(rt[y],1,n,dfn[x],1); upda(rt[y],1,n,dfn[y],1); upda(rt[z],1,n,dfn[x],-1); upda(rt[z],1,n,dfn[y],-1); if(fa[z]){ upda(rt[fa[z]],1,n,dfn[x],-1); upda(rt[fa[z]],1,n,dfn[y],-1); } } sol(1); // cout<<" 00 "<<rt[0]<<" "<<t[0].ans<<" "<<t[0].ls<<" "<<t[0].rs<<" "<<t[0].le<<" "<<t[0].ri<<" "<<t[0].tag<<endl; ans/=2; ot(ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */