Luogu P2495 [SDOI2011]消耗战

problem

Solution

苦思冥想稍作思考之后可以得到一个树形DP的方法：
令\(w(u,v)\)表示u，v之间的边的权值，\(f[u]\)表示以\(u\)为根的子树（不含\(u\)）中所有关键点与根断开的最小代价，则转移方程为：

复杂度为\(O(nm)\)，显然不正确

对于每次询问可以建立一颗虚树，边权为关键点之间最小的权值

在这道题中，如果一个关键点\(u\)的祖先中有关键点\(v\)，那么\(u\)是不需要加入虚树的，因为\(v\)一定需要断开，同时也就断开了\(u\)

Code

#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 250005
using namespace std;
typedef long long ll;

const ll inf=0x7f7f7f7f7f7f7f7f;
int n,m,k,h[maxn];
int dep[maxn],dfn[maxn],sign,prt[maxn][21],key[maxn];
ll dp[maxn],mnc[maxn][21];

struct edge
{
	int u,v,nxt;
	ll w;
};

namespace Ori
{
	edge g[maxn*2];
	int head[maxn],ecnt;
	void eADD(int u,int v,ll w)
	{
		g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].w=w;g[ecnt].nxt=head[u];head[u]=ecnt;
	}
}

namespace New
{
	edge g[maxn];
	int head[maxn],ecnt;
	void eADD(int u,int v,ll w)
	{
		g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].w=w;g[ecnt].nxt=head[u];head[u]=ecnt;
	}
	void Inti()
	{
		for(register int i=1;i<=ecnt;++i)
			g[i].u=g[i].v=g[i].nxt=0,g[i].w=0LL;
		ecnt=0;
	}
}

void dfs(int u,int fa,int depth,ll w)
{
	dep[u]=depth,prt[u][0]=fa,mnc[u][0]=w,dfn[u]=++sign;
	for(register int i=1;(1<=0;--i)
		if(dep[prt[x][i]]>=dep[y])
			x=prt[x][i];
	if(x==y)
		return x;
	for(register int i=20;i>=0;--i)
		if(prt[x][i]!=prt[y][i])
			x=prt[x][i],y=prt[y][i];
	return prt[x][0];
}

bool cmp(const int &a,const int &b)
{
	return dfn[a]=0;--i)
		if(dep[prt[u][i]]>=dep[v])
			re=min(re,mnc[u][i]),u=prt[u][i];
	return re;
}

int top,stk[maxn];
void Build()
{
	for(register int i=1;i<=k;++i)
	{
		if(top==1)
		{
			stk[++top]=h[i];
			continue;
		}
		int lca=LCA(stk[top],h[i]);
		if(lca==stk[top])
			continue;
		while(top>1 && dfn[stk[top-1]]>=dfn[lca])
			New::eADD(stk[top-1],stk[top],getmnc(stk[top-1],stk[top])),--top;
		if(lca!=stk[top])
			New::eADD(lca,stk[top],getmnc(lca,stk[top])),stk[top]=lca;
		stk[++top]=h[i];
	}
	while(top-1)
		New::eADD(stk[top-1],stk[top],getmnc(stk[top],stk[top-1])),--top;
}

void DP(int u)
{
	dp[u]=0;
	if(!New::head[u])
		return;
	for(register int i=New::head[u];i;i=New::g[i].nxt)
	{
		int v=New::g[i].v;
		DP(v);
		if(key[v])
			dp[u]+=New::g[i].w;
		else
			dp[u]+=min(New::g[i].w,dp[v]);
	}
	New::head[u]=0;
}

int main()
{
	scanf("%d",&n);
	for(register int i=1;i