前言

也是成功辅助了一道思维难度比较低的数据结构题。

我真的服了，被固化思路硬控了一个多小时，后来因为不想和父母说比赛时间，本来他们也不想我打，一直想我全身心投入 whk，就中途有两小时左右去外面和父母吃饭去了。

回来以后时间就不多了，转变思路后，最后一个小时狂敲下面常数不大的 $O(m\log m\log n+q\log n)$ 并调了半个小时的代码，也是在比赛结束前 $5$ 分钟一发过掉了这道题。

可能造数据的没有刻意卡这份代码的时间，卡常都不用就过了。说在开头，虽然非常容易想，时间复杂度也正确，但这并不是一种好写的做法。

题目大意

给定一棵以 $1$ 为根大小为 $n~(n\le 5\times 10^5)$ 的有根树，并给定一个长度为 $m~(m\le 5\times 10^5)$ 的标号序列 $a$，序列上的每个数表示树上的某个点，并有 $q~(q\le 5\times 10^5)$ 组询问，每次询问给定三个正整数 $l,r,u$，表示询问 $\max\limits_{i=l}^{r}\operatorname{lca}(a_i,u)$。

思路总结

和正解的思路差不多，但是没有一个主要算法是一样的。

首先要注意到不需要强制在线，考虑离线做法，看到询问的一段区间，并且是取 $\max$，即区间信息可直接合并，我想的方向是猫树分治，考虑如何加入一个点，因为平常我不怎么接触建虚树，没往那方向想，第一思路是用重链剖分，根据经典 trick 将贡献分成轻重儿子，如果知道这步怎么做的可以直接跳过下面板块。

::::info[也许比较详细清晰的表述]

具体地，就是对于一条存在 $u$ 的重链，若 $u$ 到当前重链顶端的链上某个点 $x~(u\neq x)$ 的某个轻儿子子树中存在一个点被添加了，那么就会对答案造成 $x$ 的贡献。对于这种情况，在添加一个点时，跳重链到根，从一条重链顶端跳父亲到另外一条重链时，将此时要到的父亲 $fa$ 的权值设成 $fa$。查询时跳 $u$ 到当前重链顶端时只用区间求 $\max$，可用线段树或树状数组（每条链分开维护）去做。

另一种情况就是查询时不一定会直接跳到根，存在从某条重链顶端跳父亲到另一条重链的情况。设此时的父亲为 $fa$，此时就不能直接和 $fa$ 的权值取 $\max$，因为有可能当且仅当存在一个被添加的点能到达 $fa$，但就在当前点的子树中，此时 $\operatorname{lca}$ 就不是 $fa$。那么只用对于每个点 $x$ 都记录某个儿子子树存在添加的点、是否存在其它儿子的子树有点被添加，询问时简单判断即可。

严谨来说还有种情况：$\operatorname{lca}$ 就是询问的点，太过简单不必赘述。

::::

这样添加一个点或询问都是 $O(\log^2 n)$ 的，时间复杂度是 $O(m\log^2 n\log m+q\log^2 n)$，但好像本校有大佬卡了很久常后跑过去了，应该就是上述的重链剖分做法。

我要正确时间复杂度！我会全局平衡二叉树！可能就是太菜了，当时我想到用这个算法优化却没有想到对于这道题的性质直接建虚树就好了，码量直接翻倍。

当发现重链剖分每次的添加和查询满足从某个点一直跳到根、取最大最小值、覆盖的区间是直接到链头或直接到链尾这三个条件时，我的第一思路就是将重链剖分换成全局平衡二叉树，以此优化掉一只 $\log$，既然是写题解，那么我需要讲一讲全局平衡二叉树。

::::info[不是很详细的讲述，也许易懂]

全局平衡二叉树最重要的是建树。还是参考重链剖分的剖分形态，对于每一条重链，根据重链上每个点以其轻儿子子树总大小为权重，保证中序遍历顺序不变的情况下重构这条重链成一棵二叉树，即二叉搜索树，根据权重取尽量平均地取到某个点（二分或暴力枚举找都可以），以这个点为此时的根，往下分别递归左半部分和右半部分并分别将它们的根作为左右儿子，此处连的是实边，最后建成一棵二叉搜索树，并将这棵树的根与原树上重链顶端的父亲连一条虚边。此处的虚边表示只能从该儿子访问父亲，其父亲访问不到它。

:::info[以上的建树环节用代码写出来]

int chain(int L,int R){
    int l=L,r=R,sum=psum[R]-psum[L-1],res=0,resmin=sum,mid,presum;
    while(l<=r){
        mid=(l+r)>>1,presum=psum[mid]-psum[L-1];
        if(labs(sum-presum)<resmin){
            res=mid;
            resmin=labs(sum-presum);
        }
        if(2*presum>=sum)
            r=mid-1;
        else
            l=mid+1;
    }
    int proot=nd[res];
    if(res>L) ls(proot)=chain(L,res-1),bfa[ls(proot)]=proot;
    if(res<R) rs(proot)=chain(res+1,R),bfa[rs(proot)]=proot;
    return proot;
}
int build_BBT(int x){
    int u=x;
    do{
        for(int i=ls[u];i;i=nx[i]){
            int v=to[i];
            if(v==wson[u]||v==sfa[u])
                continue;
            bfa[build_BBT(v)]=u;
        }
        u=wson[u];
    }while(u!=0);
    int pcnt=0;
    do{
        nd[++pcnt]=x;
        psum[pcnt]=psum[pcnt-1]+(siz[x]-siz[wson[x]]);
        x=wson[x];
    }while(x!=0);
    int p=chain(1,pcnt);top[p]=nd[1];
    return p;
}

:::

建出全局平衡二叉树后，后面的操作可以随心所欲。维护的东西还是一样的，现在将一条重链变成一颗二叉搜索树，那么可以根据中序遍历贡献到二叉搜索树的某些点上，在求答案时暴力往上跳时算上贡献即可。

真要用文字详细讲是非常麻烦的，但是只需要拿出一组数据，将全局平衡二叉树建出来，然后观察和发现贡献的方式，注意根据中序遍历的性质，将贡献挂在跳到的点上，计算答案时再处理。类似重链剖分做法，还要特别处理从一棵二叉搜索树根跳出去时的贡献。对于不同的题挂贡献也许需要不同的方法，这要具体问题具体分析。

最坏情况下树高是 $2\log n$ 的，因此能够优化掉一只 $\log$，并不建议在重要的考场上写，因为本蒟蒻认为处理贡献的部分需要考虑的东西实在是太多了，要树上维护的值也比较多，如果打代码时大脑思路不清晰等着调一辈子吧（没有开玩笑）。

如果不嫌弃本人的代码可以根据代码去进一步理解，主要的算法思路就是以上这些。

::::

经过全局平衡二叉树的优化，代码时间复杂度变成了 $O(m\log n\log m+q\log n)$，常数较小，时间限制给到五秒，可以直接在不卡常的情况下通过本题，但比较极限，qoj 上要跑 4.7s。

::::info[仅供参考的代码]

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7;
int n,m,Q,a[N],sfa[N];
int root,bfa[N],wson[N],psum[N],nd[N],top[N],val[N],ans[N];
int numvis[N],rnode[N],qmax[N],qumax[N];
bool vis[N],uvis[N];
int ls[N],nx[N<<1],to[N<<1],cnt;
int siz[N],son[2][N];
void dfs_first(int u){
    siz[u]=1;
    for(int i=ls[u];i;i=nx[i]){
        int v=to[i];
        if(v==sfa[u]) continue;
        sfa[v]=u;
        dfs_first(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[wson[u]])
            wson[u]=v;
    }
}
#define ls(x) son[0][x]
#define rs(x) son[1][x]
int chain(int L,int R){
    int l=L,r=R,sum=psum[R]-psum[L-1],res=0,resmin=sum,mid,presum;
    while(l<=r){
        mid=(l+r)>>1,presum=psum[mid]-psum[L-1];
        if(labs(sum-presum)<resmin){
            res=mid;
            resmin=labs(sum-presum);
        }
        if(2*presum>=sum)
            r=mid-1;
        else
            l=mid+1;
    }
    int proot=nd[res];
    if(res>L) ls(proot)=chain(L,res-1),bfa[ls(proot)]=proot;
    if(res<R) rs(proot)=chain(res+1,R),bfa[rs(proot)]=proot;
    return proot;
}
int build_BBT(int x){
    int u=x;
    do{
        for(int i=ls[u];i;i=nx[i]){
            int v=to[i];
            if(v==wson[u]||v==sfa[u])
                continue;
            bfa[build_BBT(v)]=u;
        }
        u=wson[u];
    }while(u!=0);
    int pcnt=0;
    do{
        nd[++pcnt]=x;
        psum[pcnt]=psum[pcnt-1]+(siz[x]-siz[wson[x]]);
        x=wson[x];
    }while(x!=0);
    int p=chain(1,pcnt);top[p]=nd[1];
    return p;
}
inline void checkmax(int &a,int b){if(b>a)a=b;}
inline void update(int x){
    int u=x,lst=N-1,lslca=x;
    checkmax(qmax[u],u),vis[u]=true;
    while(u>0){
        if(lst==ls(u)) checkmax(qmax[u],lslca);
        if(lst==rs(u)) vis[u]=true;
        lst=u,u=bfa[u];
        if(top[lst]>0&&u>0){
            if(ls(u)>0) uvis[ls(u)]=true;
            lslca=u;
            if(rs(u)>0)
                checkmax(qumax[rs(u)],lslca);
            if(numvis[u]==0)
                numvis[u]=1,rnode[u]=lst;
            else if(numvis[u]==1){
                if(rnode[u]!=lst)
                    numvis[u]=2;
            }
        }
    }
}
inline void clear(int x){
    int u=x,lst=N-1;
    qmax[u]=0,vis[u]=false;
    while(u>0){
        qmax[u]=0,vis[u]=false;
        lst=u,u=bfa[u];
        if(top[lst]>0&&u>0){
            qumax[rs(u)]=0,uvis[ls(u)]=false;
            numvis[u]=0,rnode[u]=0;
        }
    }
}
inline int calc(int x){
    int u=x,lst=u,ans=0,lslca=u;
    checkmax(ans,qumax[u]);
    if(vis[u]==true) checkmax(ans,u);
    if(uvis[u]==true) checkmax(ans,u);
    checkmax(ans,qmax[u]);
    if(numvis[u]>0) checkmax(ans,u);
    while(u>0){
        checkmax(ans,qumax[u]);
        if(uvis[u]==true)
            checkmax(ans,lslca);
        if(lst==ls(u)){
            if(vis[u]==true||numvis[u]>0)
                checkmax(ans,lslca);
        }
        if(lst==rs(u)){
            checkmax(ans,qmax[u]);
            if(numvis[u]>0)
                checkmax(ans,u);
        }
        lst=u,u=bfa[u];
        while(top[lst]>0&&u>0){
            lslca=u;
            if(vis[u]==true||uvis[u]==true)
                checkmax(ans,u);
            checkmax(ans,qmax[u]);
            checkmax(ans,qumax[u]);
            if((numvis[u]>0&&lst!=rnode[u])||(numvis[u]==2))
                checkmax(ans,u);
            lst=u,u=bfa[u];
        }
    }
    return ans;
}
struct queries{int l,r,u,id;};
struct ree{int u,id;};
vector<ree> cl[N];
vector<queries> allq;
void solve(int l,int r,vector<queries> &now){
    int mid=(l+r)>>1;
    if(l<r){
        vector<queries> L,R,M;
        for(queries i:now){
            if(i.r<=mid) L.push_back(i);
            else if(i.l>mid) R.push_back(i);
            else M.push_back(i);
        }
        now.swap(M);
        solve(l,mid,L),solve(mid+1,r,R);
    }
    if(now.empty()) return ;
    int lmin=now.front().l;
    int rmax=now.front().r;
    for(queries i:now){
        lmin=min(lmin,i.l),cl[i.l].push_back({i.u,i.id});
        rmax=max(rmax,i.r),cl[i.r].push_back({i.u,i.id});
    }
    for(int i=mid;i>=lmin;--i){
        update(a[i]);
        for(ree j:cl[i]) checkmax(ans[j.id],calc(j.u));
    }
    for(int i=mid;i>=lmin;--i){
        clear(a[i]);
        cl[i].clear();
    }
    for(int i=mid+1;i<=rmax;++i){
        update(a[i]);
        for(ree j:cl[i]) checkmax(ans[j.id],calc(j.u));
    }
    for(int i=mid+1;i<=rmax;++i){
        clear(a[i]);
        cl[i].clear();
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>Q;
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v;
        nx[++cnt]=ls[u],to[ls[u]=cnt]=v;
        nx[++cnt]=ls[v],to[ls[v]=cnt]=u;
    }
    for(int i=1;i<=m;++i)
        cin>>a[i];
    root=1;
    dfs_first(root),build_BBT(root);
    for(int i=1,l,r,u;i<=Q;++i){
        cin>>l>>r>>u;
        allq.push_back({l,r,u,i});
    }
    solve(1,m,allq);
    for(int i=1;i<=Q;++i)
        cout<<ans[i]<<"\n";
    return 0;
}

::::

注意以上做法在洛谷的评测机上跑不过去。

所以我顺便把正解也讲了：

往虚树上想，为方便左右区间虚树的合并，不能再用猫树分治，那就改成线段树分治就好了。将询问拆成 $\log n$ 个区间，然后在线段树上处理每个区间包含的关键点的虚树即可（线段树的底层是 $a_{1\sim m}$）。

设当前区间为 $[l,r]$，先考虑虚树上的关键点是什么，显然一定要有 $a_{l\sim r}$，然后还有就是该节点上的询问的点、所有关键点的 $\operatorname{lca}$。

合并左右两边的虚树，本质上就是合并两边的 $a$，问题就在于不能直接按照 $\operatorname{dfn}$ 排序，会使时间复杂度多一个 $\log$，那么对于 $a$ 可以从左右区间的 $a$ 归并上来，而对于询问，那么只用先将询问中的 $u$ 按 $\operatorname{dfn}$ 从小到大排序并逐次加入线段树，得出所有关键点的过程都用归并。而对于建虚树的部分用栈来建，而建虚树过程中的 $\operatorname{lca}$ 用 $O(n\log n)-O(1)$ 的求法，用欧拉序或 $\operatorname{dfn}$ 序都行。

建出虚树后要统计答案，那么考虑一个询问的 $u$，在虚树上，对该询问有贡献的点一定是 $u$ 到根的路径上的点 $v$ 并满足 $v$ 的儿子子树中去除包含 $u$ 的儿子子树，其它的儿子子树中仍然存在 $a_{l\sim r}$ 任意一个点，贡献为 $v$；或者 $u$ 的子树中存在 $a_{l\sim r}$ 任意一个点，贡献为 $u$。可以将所有 $a_{l\sim r}$ 标记为 $1$，第一遍 dfs 求出对于每个虚树上的点求出子树中这些 $1$ 的和，第二次 dfs 根据求出的和判断是否对下面的点产生贡献即可。

难点就是保证时间复杂度是 $O(n\log n)$ 级别，时间复杂度为 $(m+n)\log m+q$，可以轻松过掉本题。

::::info[仅供参考的代码]

#include<bits/stdc++.h>
using namespace std;
namespace Fast_IO{
    FILE *fin=stdin,*fout=stdout;
    const int BUF=1<<20;
    char rbuf[BUF],*p1=rbuf,*p2=rbuf,wbuf[BUF],*p3=wbuf;
    inline void flush_read(){p1=p2=rbuf;}
    inline char _getchar(){return (p1==p2)&&(p2=(p1=rbuf)+fread(rbuf,1,BUF,fin),p1==p2)?EOF:*p1++;}
    inline void flush_write(){fwrite(wbuf,1,p3-wbuf,fout),p3=wbuf;}
    inline void _putchar(char ch){*p3++=ch;if(p3-wbuf==BUF)flush_write();}
    template<typename T>
    inline void read(T &x){
        x=0;static char ch;T f=1;
        do{ch=_getchar();if(ch=='-')f=-f;}while(!isdigit(ch));
        do{x=(x<<1)+(x<<3)+(ch^48);ch=_getchar();}while(isdigit(ch));
        x*=f;
    }
    inline void read(string &str){
        static char ch;
        str.clear();
        do ch=_getchar();while(ch=='\n'||ch==' '||ch=='\r'||ch=='\t');
        do str.push_back(ch),ch=_getchar();while(ch!='\n'&&ch!=' '&&ch!='\r'&&ch!='\t'&&ch!=EOF);
    }
    inline void read(char *chr){
        static char ch;
        do ch=_getchar();while(ch=='\n'||ch==' '||ch=='\r'||ch=='\t');
        do *chr++=ch,ch=_getchar();while(ch!='\n'&&ch!=' '&&ch!='\r'&&ch!='\t'&&ch!=EOF);
        *chr='\0';
    }
    template<typename T,typename... Args>
    inline void read(T &x,Args &...args){read(x),read(args...);}
    template<typename T>
    inline void write(T x){
        if(x<0)_putchar('-'),x=-x;
        static char stack[1<<9],*tmp;
        tmp=stack;
        do*tmp++=(x%10)^48;while(x/=10);
        while(tmp!=stack)_putchar(*--tmp);}
    inline void write(const char ch){_putchar(ch);}
    inline void write(const char *ch){while((*ch)!=0)_putchar(*ch++);}
    inline void write(const string str){for(char ch:str)_putchar(ch);}
    template<typename T,typename... Args>
    inline void write(T x,Args... args){write(x),write(args...);}
    class Flush{public:~Flush(){flush_write();}}tmp;
}using Fast_IO::read;using Fast_IO::write;
constexpr int N=5e5+7,logN=19;
int n,m,Q,a[N],dfn[N],tot,siz[N],nd[N];
int ls[N],nx[N<<1],to[N<<1],cnt,root;
int stmin[logN+1][N];
int stk[N],ans[N],pre[N],lg2[N],pans[N];
struct queries{int l,r,u,id;}allq[N];
vector<int> now[N<<2],E[N];
#define vsize(x) ((int)x.size())
inline int dfnmin(int a,int b){return (dfn[a]<dfn[b])?a:b;}
void dfs(int u,int FA){
	dfn[u]=++tot,nd[tot]=u;
	stmin[0][tot]=FA;
	for(int i=ls[u];i;i=nx[i]){
		int v=to[i];
		if(v==FA) continue;
		dfs(v,u);
	}
}
#define lx (x<<1)
#define rx (x<<1|1)
void insert(int l,int r,int L,int R,int id,int x){
	if(L>R) return ;
	if(L<=l&&r<=R)
		return now[x].push_back(id),void();
	int mid=(l+r)>>1;
	if(L<=mid)
		insert(l,mid,L,R,id,lx);
	if(mid<R)
		insert(mid+1,r,L,R,id,rx);
	return ;
}
inline int lca(int u,int v){
	u=dfn[u],v=dfn[v];
	if(u==v) return u;
	if(u>v) swap(u,v);
	int p=lg2[v-u];
	return dfnmin(stmin[p][u+1],stmin[p][v-(1<<p)+1]);
}
void dfs_first(int u){
	pans[u]=0;
	for(int v:E[u]){
		dfs_first(v);
		siz[u]+=siz[v];
	}
}
void dfs_second(int u){
	for(int v:E[u]){
		pans[v]=pans[u];
		if(siz[u]>siz[v])
			pans[v]=max(pans[v],u);
		dfs_second(v);
	}
	if(siz[u]>0)
		pans[u]=max(pans[u],u);
}
void solve(int l,int r,int x){
	if(l<r){
		int mid=(l+r)>>1;
		solve(l,mid,lx),solve(mid+1,r,rx);
		int p=mid+1,j=l;
		for(int i=l;i<=mid;++i){
			while(p<=r&&dfn[a[p]]<dfn[a[i]])
				pre[j++]=a[p++];
			pre[j++]=a[i];
		}
		for(int i=l;i<j;++i) a[i]=pre[i];
	}
	if(now[x].empty()) return ;
	int len=0;
	{
		int p=0;
		for(int i=l;i<=r;++i){
			while(p<vsize(now[x])&&dfn[allq[now[x][p]].u]<dfn[a[i]]){
				if(allq[now[x][p]].u!=pre[len])
					pre[++len]=allq[now[x][p]].u;
				++p;
			}
			if(a[i]!=pre[len]) pre[++len]=a[i];
		}
		while(p<vsize(now[x])){
			if(allq[now[x][p]].u!=pre[len])
				pre[++len]=allq[now[x][p]].u;
			++p;
		}
	}
	for(int i=1;i<=len;++i)
		E[pre[i]].clear(),siz[pre[i]]=0;
	int top=1;stk[top]=root;
	E[1].clear(),siz[1]=0;
	for(int i=1+(pre[1]==root);i<=len;++i){
		int p=lca(stk[top],pre[i]);
		if(p!=stk[top]){
			while(dfn[stk[top-1]]>dfn[p]){
				E[stk[top-1]].push_back(stk[top]);
				--top;
			}
			if(stk[top-1]!=p){
				E[p].clear(),siz[p]=0;
				E[p].push_back(stk[top]);
				stk[top]=p;
			}
			else{
				E[p].push_back(stk[top--]);
			}
		}
		stk[++top]=pre[i];
	}
	while(top>1){
		E[stk[top-1]].push_back(stk[top]);
		top--;
	}
	for(int i=l;i<=r;++i)
		siz[a[i]]=1;
	dfs_first(root),dfs_second(root);
	for(int i:now[x])
		ans[allq[i].id]=max(ans[allq[i].id],pans[allq[i].u]);
}
int main(){
	lg2[0]=-1;
	for(int i=1;i<N;++i) lg2[i]=lg2[i>>1]+1;
	read(n,m,Q);
	for(int i=1,u,v;i<n;++i){
		read(u,v);
		nx[++cnt]=ls[u],to[ls[u]=cnt]=v;
		nx[++cnt]=ls[v],to[ls[v]=cnt]=u;
	}
	for(int i=1;i<=m;++i)
		read(a[i]);
	for(int i=1;i<=Q;++i){
		read(allq[i].l,allq[i].r,allq[i].u);
		allq[i].id=i;
	}
	root=1,dfs(root,root);
	for(int j=1;j<20;++j)for(int i=2;i+(1<<j)-1<=n;++i)
		stmin[j][i]=dfnmin(stmin[j-1][i],stmin[j-1][i+(1<<(j-1))]);
	sort(allq+1,allq+Q+1,[](queries a,queries b){return dfn[a.u]<dfn[b.u];});
	for(int i=1;i<=Q;++i)
		insert(1,m,allq[i].l,allq[i].r,i,1);
	solve(1,m,1);
	for(int i=1;i<=Q;++i)
		write(ans[i],'\n');
	return 0;
}

::::

后语

以上是一个不正经的人写的一篇正经的题解，如果有不懂的欢迎私信。

代码中全局平衡二叉树中贡献方法是我自己摸索出来的，若有更好的实现方法，请私信不吝赐教。