题外话
-
此做法的主要思路来自 图老师，比较巧妙的转化！至少对于我来说，比洛谷题解区的题解都要简单！
-
\(odt\) 被卡掉了，好伤心/ll（upd：图老师说 \(odt\) 不会被卡，他坚信是我代码有问题/yun
-
今天的饭好难吃/ng
\(\text{Links}\)
题意
给出一棵有 \(n\) \((n\le 10^5)\) 个节点的数，和一个长度为 \(m\) \((m\le n)\) 的节点序列 \(c\)，你需要回答 \(q\) \((q\le 10^5)\) 次询问（非强制在线），每次给出 \(l,r\) \((1\le l\le r\le m)\)，求最小的包含 \(c\) 中 \([l,r]\) 内的节点的连通块的大小。
题解
考虑将询问挂在右端点，然后离线下来扫描，每次将 \(1\) 到 \(c_i\) 的路径上的点全都染上颜色 \(i\)，然后如果此处挂了询问，则答案为此询问中所有节点的 \(lca\) 的子树内颜色 \(col\le l\) 的点数，即 \(\sum_{v\in sub_u}[col_v\le l]\)。正确性懒得讲了（。这个转化让我觉得好的地方除了染色还有它巧妙地避开了暴力想法中动态更新 \(lca\) 然后开 \(vis\) 染色的麻烦（虽然这个转化可能其实挺常规，不过反正是让我觉得挺好的），图老师好强/ll/ll/ll orz。
然后这就特别简单了啊，染色部分可以像图老师场切做法那样分块，也可以像我一样偷懒用 \(odt\)（虽然我的貌似有点问题然后 T 了），\(lca\) 部分随便搞， \(\text{ST}\) 或者 \(\text{SegT}\) 都行。
还是放一下代码吧，虽然 T 了还没调过，但是不得不说这个做法用 \(odt\) 实现真的很好写！
\(\text{Code:}\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
const int N=1e5+113;
int n,m,k,idx,head[N],ans[N],c[N];
int id[N],son[N],fa[N],dep[N],siz[N],top[N];
int st[N][25],flog[N],fpow[25];
struct edge{
int u,v,nxt;
}e[N<<1];
il void adde(int u,int v){
e[++idx]={u,v,head[u]};
head[u]=idx;
}
il void dfs1(int x,int father,int depth){
fa[x]=father,dep[x]=depth,siz[x]=1;
for(re int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa[x])continue;
dfs1(v,x,depth+1);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]])son[x]=v;
}
}
il void dfs2(int x,int top_now){
top[x]=top_now,id[x]=++idx;
if(!son[x])return;
dfs2(son[x],top_now);
for(re int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa[x]||v==son[x])continue;
dfs2(v,v);
}
}
il int Lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
il void GetST(){
fpow[0]=1;
for(re int i=1;i<=20;i++)fpow[i]=fpow[i-1]<<1;
for(re int i=2;i<=k;i++)flog[i]=flog[i>>1]+1;
for(re int i=1;i<=k;i++)st[i][0]=c[i];
for(re int i=1;i<=flog[k];i++)
for(re int j=1;j+fpow[i]-1<=k;j++)
st[j][i]=Lca(st[j][i-1],st[j+fpow[i-1]][i-1]);
}
il int GetLca(int l,int r){
int len=flog[r-l+1];
return Lca(st[l][len],st[r-fpow[len]+1][len]);
}
struct Chtholly{
int l,r;
mutable int val;
Chtholly(int l,int r=0,int val=0):l(l),r(r),val(val){}
il bool operator<(const Chtholly &a)const{
return l<a.l;
}
};
set<Chtholly>s;
#define It set<Chtholly>::iterator
il It Split(int pos){
It fnd=s.lower_bound(Chtholly(pos));
if(fnd!=s.end()&&fnd->l==pos)return fnd;
if((--fnd)->r<pos)return s.end();
int l=fnd->l,r=fnd->r,val=fnd->val;
s.erase(fnd);
s.insert(Chtholly(l,pos-1,val));
return s.insert(Chtholly(pos,r,val)).first;
}
il void Assign(int l,int r,int val){
It R=Split(r+1),L=Split(l);
s.erase(L,R);
s.insert(Chtholly(l,r,val));
}
il int GetAns(int l,int r,int x){
It R=Split(r+1),L=Split(l);
int res=0;
for(re It i=L;i!=R;i++)
if(i->val>=x)res+=i->r-i->l+1;
return res;
}
il void Assign_Path(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
Assign(id[top[x]],id[x],z);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
Assign(id[y],id[x],z);
}
il int GetAns_Subt(int x,int y){
return GetAns(id[x],id[x]+siz[x]-1,y);
}
struct query{
int l,r,id;
}q[N];
il bool cmp(query x,query y){
return x.r<y.r;
}
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int main(){
n=read(),k=read(),m=read();
for(re int i=1;i<n;i++){
int u=read(),v=read();
adde(u,v),adde(v,u);
}
idx=0;
dfs1(1,0,0);
dfs2(1,1);
for(re int i=1;i<=k;i++)c[i]=read();
GetST();
for(re int i=1;i<=m;i++)
q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+1+m,cmp);
int pos=0;
s.insert(Chtholly(1,n,0));
for(re int i=1;i<=m;i++){
int l=q[i].l,r=q[i].r;
int lca=GetLca(l,r);
while(pos<r)pos++,Assign_Path(1,c[pos],pos);
ans[q[i].id]=GetAns_Subt(lca,q[i].l);
}
for(re int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}