https://www.lydsy.com/JudgeOnline/problem.php?id=2286
wa了两次因为lca犯了zz错误
这道题如果不多次询问的话就是裸dp。
一棵树上多次询问,且总共询问的点数较小(能够承受得住加个logn的复杂度(常数就不管了,按理说还要*2吧))可以用虚树来处理。
虚树就是对每次询问将有用的点建一棵树,每次询问查询m个点,则这棵树最多m*2个点(太优秀了)。
这个虚树的建立过程是用栈维护一条链,每加入一个点就把她和前一条链的叶子节点的lca和这个点本身加入虚树中,然后将当前链的叶子节点改为当前加入的点。
dfs序是个好东西,它帮助维护了这条链和后面点的关系(的逻辑性?(看到代码就懂了吧,反正就很有逻辑就对了))。
所以我之前为什么要学树链剖分,树链剖分什么用都没有嘤嘤嘤,最喜欢倍增了。(日常抛弃旧爱)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define LL long long
const int maxn=;
const LL minf=(LL)5e17;
int n,m;
struct nod{
int nex,y,v;
};nod e[maxn*];nod e1[maxn*];
int head[maxn]={},tot=;
int head1[maxn]={},tot1=;
int id[maxn]={},cnt=;
int fa[maxn][]={},dep[maxn]={};
LL dis[maxn]={},f[maxn]={};
int a[maxn]={},tly=;
int sta[maxn]={},tai=;
inline int mread(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void init(int x,int y,int v){
e[++tot].y=y;e[tot].v=v;e[tot].nex=head[x];head[x]=tot;
}
inline void init1(int x,int y){
if(x==y)return;
e1[++tot1].y=y;e1[tot1].nex=head1[x];head1[x]=tot1;
}
void dfs(int x,int pa){
fa[x][]=pa;id[x]=++cnt;
for(int i=;fa[fa[x][i-]][i-]!=;++i)fa[x][i]=fa[fa[x][i-]][i-];
for(int i=head[x];i;i=e[i].nex){
int y=e[i].y;
if(y==pa)continue;
dis[y]=dis[x]<e[i].v?dis[x]:e[i].v;
dep[y]=dep[x]+;
dfs(y,x);
}
}
bool mcmp(int x,int y){return id[x]<id[y];}
int getlca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=;i>=;--i){
if(!fa[x][i])continue;
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(dep[x]==dep[y])break;
}
if(x==y)return x;
for(int i=;i>=;--i){
if(!fa[x][i])continue;
if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
}
return fa[x][];
}
void dfs1(int x){
f[x]=dis[x];LL v=;
for(int i=head1[x];i;i=e1[i].nex){
dfs1(e1[i].y);
v+=f[e1[i].y];
}
if(v)f[x]=min(f[x],v);
head1[x]=;
}
void cutit(){
int q=mread(); for(int i=;i<=q;++i)a[i]=mread();
sort(a+,a++q,mcmp); tly=;
for(int i=;i<=q;++i){if(getlca(a[i],a[tly])!=a[tly])a[++tly]=a[i];}
//由根节点到叶子节点的每条链上至多只有一个点
tai=;sta[]=;tot1=;int lc;
for(int i=;i<=tly;i++){//sta按照dfs序维护了一条链
lc=getlca(sta[tai],a[i]);
for(;tai>;){//更改链向下延伸的方向,把之前方向的点连上
if(dep[sta[tai-]]<=dep[lc]){
init1(lc,sta[tai]);tai--;
if(sta[tai]!=lc)sta[++tai]=lc;
break;
}init1(sta[tai-],sta[tai]);tai--;
}
if(sta[tai]!=a[i])sta[++tai]=a[i];
}
while(--tai)init1(sta[tai],sta[tai+]);
dfs1();
printf("%lld\n",f[]);
}
int main(){
int x,y,v;
n=mread();
for(int i=;i<n;++i){
x=mread();y=mread();v=mread();
init(x,y,v);init(y,x,v);
}
dis[]=minf; dep[]=; dfs(,);
m=mread(); for(int i=;i<=m;++i) cutit();
return ;
}