虚树

每次将询问的点以及其lca单独取出来建树，使用dfs序和栈优化

//p2495
#include 
#define int long long
using namespace std;

long long read()
{
	long long res=0,p=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')p=-1; ch=getchar();}
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return res*p;
}

const int maxn=5e5+10,inf=1e15;

int n,m,sum;
int head[maxn],cnt,head1[maxn],cnt1;
int siz[maxn],son[maxn],f[maxn][30],dis[maxn],idfs[maxn],dep[maxn],ma[maxn];
bool que[maxn];
int stk[maxn<<2],top;

struct note{int nxt,to,val;}ed[maxn],ed1[maxn];

struct node{int id,num;}ki[maxn];

void add(int u,int v,int w) {ed[++cnt].to=v,ed[cnt].nxt=head[u],ed[cnt].val=w,head[u]=cnt;}

void add1(int u,int v) {ed1[++cnt1].to=v,ed1[cnt1].nxt=head1[u],head1[u]=cnt1;}

void dfs(int now)
{
	siz[now]=1,idfs[now]=++sum,dep[now]=dep[f[now][0]]+1;
	int j;
	for(j=0;f[now][j];++j) f[now][j+1]=f[f[now][j]][j];
	ma[now]=j;
	for(int i=head[now];i;i=ed[i].nxt)
	{
		int v=ed[i].to,w=ed[i].val;
		if(v==f[now][0]) continue ;
		f[v][0]=now,dis[v]=min(dis[now],w);
		dfs(v);
		siz[now]+=siz[v],++son[now];
	}
}

bool cmp(node a,node b) {return a.numdep[y]) swap(x,y);
	int delta=dep[y]-dep[x];
	for(int i=30;i>=0;--i) if(delta&(1<=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

long long dfs1(int now)
{
	long long sum=0,ans=0;
	for(int i=head1[now];i;i=ed1[i].nxt)
	{
		int v=ed1[i].to;
		sum+=dfs1(v);
	}
	if(que[now]) ans=dis[now];
	else ans=min(dis[now],sum);
	que[now]=0,head1[now]=0;
	return ans;
}

signed main()
{
	n=read();
	for(int i=1;i=dep[stk[top-1]])
				{
					if(lt!=stk[top])
					{
						add1(lt,stk[top]);
						if(lt!=stk[top-1]) stk[top]=lt;
						else --top;
					}
					break ;
				}
				add1(stk[top-1],stk[top]),--top;
			}
			stk[++top]=now;
		}
		while(--top) add1(stk[top],stk[top+1]);
		cout<