树链求并又不会写，学了一发虚树，再也不虚啦~
2286: [Sdoi2011]消耗战
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 5002 Solved: 1869
[Submit][Status][Discuss]
Description
在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。
Input
第一行一个整数n，代表岛屿数量。
接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。
第n+1行，一个整数m，代表敌方机器能使用的次数。
接下来m行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,…hk，表示资源丰富岛屿的编号。
Output
输出有m行，分别代表每次任务的最小代价。
Sample Input
10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6
Sample Output
12
32
22
32
22
如题，就是做虚树+树形dp。
虚树是什么呢？他是针对原来的树，剔除对结果无影响的点，剩下的点连接起来的一颗新的树。这样的树可以尽可能的避免对无影响点的计算，从而降低求解的时间复杂度。
这样的一颗虚树能降低时间复杂度的前提要求是，建立这颗树时间为O(k）,空间为O(k),k为影响点的数目。
首先我们想到针对每个任务的朴素做法。先dfs向下求每个点和根割离的最小代价val[u]。然后针对目标点，dfs向上的时候求每个点u的最小代价dp[u]=min(Σdp[son[u]],val[u])，其中son[u]为u的孩子节点，而任务目标点的dp[u]初值为val[u]，其余为0。这样的确能做出来，但是时间复杂度爆炸。岛屿数为n，任务数为m。那么时间复杂度O(mn）肯定过不了的，巨爆炸。
但我们观察到ΣKi是≤50w的。首先我们算出val[u]。我们对于每个任务，分别建立一个空间为O(Ki)的虚树。我们在这颗书上做树形dp。这样我们时间复杂度也就降到了O(ΣKi)了。
那每个任务的影响点有哪些呢？很明显的任务给出的丰富节点和他们的lca、根节点1为影响点。首先k个点的lca一定小于k个，这个我就不在这里证明了。那么接下来就是求lca点了。我们把所有丰富节点按照dfs序排序，然后每相邻两个求lca。这些点就是所有的lca点了。注意lca点和丰富节点可能是同一个点，所以记得标记一下。
然后我们求每个点他们的父亲。求父亲的话你要多想想dfs时间戳的性质-每个节点的子树是在一个连续区间上的。因此我们再把这所有影响点按dfs序排序，然后维护一个栈。从头到尾处理，每次不断弹栈直到dfs时间戳上栈顶的点的子树区间包含该处理点，那么该栈顶点就是该点的父亲了。这样求完一颗虚树就建好了。
然后在上面跑个树形dp就AC了~。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define mod 1000000007
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=5e5+;
int n,m,t,u,v;
int bit[];
struct edg
{
int next,to,val;
}edge[N];
int head[N],tot;
void addedge(int u,int v,int val)
{
edge[++tot].val=val;
edge[tot].next=head[u];
edge[tot].to=v;
head[u]=tot;
return ;
}
int fa[N][],fro[N],bac[N],clk,dep[N],pre,vfa[N],vis[N],val[N];
LL dp[N];
stack<int> sta;
int cntp,p[N],cntall;
void init()
{
clr_1(head);
tot=;
clk=;
bit[]=;
val[]=INF;
for(int i=;i<;i++)
bit[i]=bit[i-]<<;
return ;
}
void dfs(int u,int father,int deep)
{
int p;
fro[u]=++clk;
dep[u]=deep;
fa[u][]=father;
for(int i=;bit[i]<=deep;i++) fa[u][i]=fa[fa[u][i-]][i-];
// cout<<"dep["<<u<<"]:"<<deep<<" fa["<<u<<"]: ";
// for(int i=0;bit[i]<=deep;i++) cout<<fa[u][i]<<" ";
// cout<<endl;
for(int i=head[u];i!=-;i=edge[i].next)
if(edge[i].to!=father)
{
val[edge[i].to]=min(val[u],edge[i].val);
dfs(edge[i].to,u,deep+);
}
bac[u]=clk;
return ;
}
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
int tmp=dep[u]-dep[v];
for(int i=;bit[i]<=tmp;i++)
if(tmp&bit[i]) u=fa[u][i];
int i=;
while(bit[i]>dep[u]) i--;
for(i;i>=;i--)
if(fa[u][i]!=fa[v][i]) {u=fa[u][i]; v=fa[v][i];}
return u==v?u:fa[u][];
}
bool cmp(int a,int b)
{
return fro[a]<fro[b];
}
int main()
{
init();
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&u,&v,&t);
addedge(u,v,t);
addedge(v,u,t);
}
dfs(,,);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d",&cntp);
for(int i=;i<=cntp;i++)
{
scanf("%d",p+i);
vis[p[i]]=;
}
sort(p+,p+cntp+,cmp);
cntall=cntp;
for(int i=;i<=cntp;i++)
{
pre=lca(p[i],p[i-]);
// cout<<pre<<"~"<<endl;
if(!vis[pre])
{
vis[pre]=;
p[++cntall]=pre;
}
}
if(!vis[])
{
vis[]=;
p[++cntall]=;
}
sort(p+,p+cntall+,cmp);
while(!sta.empty())
sta.pop();
sta.push(p[]);
dp[p[]]=;
for(int i=;i<=cntall;i++)
{
// cout<<p[i]<<endl;
dp[p[i]]=;
while(!sta.empty() && fro[p[i]]>bac[sta.top()]) sta.pop();
vfa[p[i]]=sta.top();
sta.push(p[i]);
}
for(int i=cntall;i>;i--)
{
if(vis[p[i]]==)
dp[p[i]]=min(dp[p[i]],(LL)val[p[i]]);
else
dp[p[i]]=val[p[i]];
dp[vfa[p[i]]]+=dp[p[i]];
// cout<<p[i]<<" "<<val[p[i]]<<" "<<dp[p[i]]<<" "<<vfa[p[i]]<<endl;
}
printf("%lld\n",dp[p[]]);
for(int i=;i<=cntall;i++)
vis[p[i]]=;
}
return ;
}
这个板子太假2333。
然后我们做虚树的板子需要啥呢？
首先数据结构
struct edg
{
int next,to;
}edge[N],vedge[N];//实树和虚树的边
int head[N],vhead[N],etot,vtot;//实树和虚树的头，边总数。
int bit[];//倍增法lca需要计算2^i的值
int timed;//dfs序计数器
int dep[N],fa[N][],dfn[N];//实树点的深度，倍增lca里跃迁2^k的祖先，每个实树点对应的dfs序
int pt[N],cnt;//虚树的点和点总数
然后是需要做的函数
void init()//初始化所有条件
{
clr_1(head);
clr_1(vhead);
etot=vtot=;
bit[]=;
for(int i=;i<;i++)
bit[i]=bit[i-]<<;
timed=;
return;
}
void addedge(int u,int v)//加入实边
{
edge[++etot]=(edg){head[u],v};
head[u]=etot;
return;
}
void vaddedge(int u,int v)//加入虚边
{
vedge[++vtot]=(edg){vhead[u],v};
vhead[u]=vtot;
return;
}
void dfs(int u,int fat,int d)//一遍dfs把dfn，dep，fa[n][k]求出
{
dfn[u]=++timed;
dep[u]=d;
fa[u][]=fat;
for(int i=;bit[i]<=d;i++)
fa[u][i]=fa[fa[u][i-]][i-];
int p;
for(int i=head[u];i!=-;i=edge[i].next)
{
p=edge[i].to;
if(p==fat) continue;
dfs(p,u,d+);
}
return ;
}
int lca(int u,int v)//倍增求lca
{
if(dep[u]<dep[v]) swap(u,v);
int tmp=dep[u]-dep[v];
for(int i=;bit[i]<=tmp;i++)
if(tmp&bit[i]) u=fa[u][i];
for(int i=;i>=;i--)
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return u==v?u:fa[u][];
}
bool cmp(int a,int b)//dfn排序比较函数
{
return dfn[a]<dfn[b];
}
int sta[N],top;//暂存处理dfs链的栈和栈顶
void getvt(int *pt,int &cnt)
{
sort(pt+,pt+cnt+,cmp);
top=;
int f;
for(int i=,cntp=cnt;i<=cntp;i++)
{
if(top==) {sta[++top]=pt[i]; continue;}
f=lca(pt[i],sta[top]);
while(top> && dep[f]<dep[sta[top-]])
vaddedge(sta[top-],sta[top]),top--;
if(dep[f]<dep[sta[top]])
vaddedge(f,sta[top]),top--;
if(top> && sta[top]!=f) sta[++top]=f,pt[++cnt]=f;
sta[++top]=pt[i];
}
while(top>)
vaddedge(sta[top-],sta[top]),top--;
sort(pt+,pt+cnt+,cmp);
return ;
}