链接

　　https://www.luogu.org/problem/show?pid=3128

题解

　　实在找不到LCT模板题了，只好拿这道树剖裸题练手

　　题解：LCT直接做。

代码

//LCT #include <cstdio> #include <algorithm> #define maxn 500000 #define inf 0x3f3f3f3f using namespace std; int N, K; struct node { int w, rev, add; node *f, *ch[2]; }nd[maxn], *s[maxn]; inline int getwh(node *x) {if(!x->f)return -1;if(x->f->ch[0]==x)return 0;if(x->f->ch[1]==x)return 1;return -1;} inline bool isroot(node *x){return getwh(x)==-1;} inline void join(node *x, node *y, int wh){if(x)x->f=y;if(y)y->ch[wh]=x;} inline void rever(node *x){if(x)x->rev^=1;} inline void add(node *x, int v){if(x)x->add+=v;} inline void pushdown(node *x) { if(x->add) { x->w+=x->add; add(x->ch[0],x->add),add(x->ch[1],x->add); x->add=0; } if(x->rev) { swap(x->ch[0],x->ch[1]); rever(x->ch[0]),rever(x->ch[1]); x->rev=0; } } inline void rotate(node *x) { node *y=x->f, *z=y->f; int c=getwh(x); if(isroot(y))x->f=y->f; else join(x,z,getwh(y)); join(x->ch[!c],y,c); join(y,x,!c); } inline void splay(node *x) { node *y; int top=0; for(y=x;!isroot(y);y=y->f)s[++top]=y;s[++top]=y; for(;top;top--)pushdown(s[top]); while(!isroot(x)) { y=x->f; if(isroot(y)){rotate(x);break;} if(getwh(x)^getwh(y))rotate(x);else rotate(y); rotate(x); } } inline void access(node *x) { node *t=0; while(x) { splay(x); x->ch[1]=t; t=x;x=x->f; } } inline void makeroot(node *x){access(x);splay(x);rever(x);} inline void link(node *x, node *y){makeroot(x);x->f=y;} int main() { int i, x, y, ans=-inf; scanf("%d%d",&N,&K); for(i=1;i<N;i++)scanf("%d%d",&x,&y),link(nd+x,nd+y); for(i=1;i<=K;i++) { scanf("%d%d",&x,&y); makeroot(nd+x);access(nd+y);splay(nd+y);add(nd+y,1); } for(i=1;i<=N;i++) { splay(nd+i); ans=max(ans,nd[i].w); } printf("%d\n",ans); return 0; }