CF526G Spiders Evil Plan

一、题目

点此看题

二、解法

网上的很多题解讲的都不清楚，我还是尽量不要避重就轻??

首先不考虑连通块包含 \(x\) 的限制，考虑一个经典结论，对于一个具有 \(k\) 个叶子的无根树，我们可以构造出使用 \(\lceil\frac{k}{2}\rceil\) 条路径覆盖完树所有边的方案，并且这个构造一定是下界。

那么一个连通块合法的条件就是其叶子数 \(\leq 2y\)，我们考虑用叶子集合来表示连通块，那么选出叶子之后它们的极小连通块（也就是点数最少的导出子图，使得保留这些点之后叶子联通）就是原问题中的连通块。

然后有一个 \(\tt observation\)：在根被选取的前提下，如果 \(u\) 的子树有点被选了，那么 \(u\) 的长链一定会出现在连通块中。这是因为必然存在一条根到子树内的路径出现在连通块中，那么长链肯定在最优方案中。

如果我们先枚举根，这又是一个经典问题，我们把长链的贡献记在链顶上，那么从大到小依次选取即可。其实这就是 BZOJ攻略，证明的话可以考虑建出网络流模型，然后不会发生退流操作。

因为直径的某个端点一定作为叶子被选取了，所以我们可以以直径的某个端点为根计算答案，然后取最大值即可。

最后考虑包含 \(x\) 的限制，如果前 \(2y-1\) 条长链已经包含 \(x\) 是最好的。否则我们考虑调整法，先加入前 \(2y-2\) 条长链，然后调整的方案是这两种情况之一：

• 最后一条长链不选，转而选取 \(x\) 所在的长链。
• 最后一条长链选，我们找到离 \(x\) 最近的长链，把它最下面一段替换成 \(x\) 所在的长链。

可以简单的用倍增实现（把长链排名放在点上），时间复杂度 \(O(n\log n)\)

三、总结

懂得套用一些经典结论来思考图论问题。

边权和贡献最大问题可以往长链剖分贪心这个角度考虑。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 100005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,tot,zxy,ans,f[M];
struct edge {int v,c,next;}e[M<<1];
struct graph
{

int rt,fa[M][20],g[M][20],dep[M];
int k,son[M],len[M],top[M],sum[M],rnk[M];
void find(int u,int fa)
{
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dep[v]=dep[u]+e[i].c;
		find(v,u);
	}
}
void dfs(int u,int p)
{
	for(int i=1;i<20;i++)
	{
		fa[u][i]=fa[fa[u][i-1]][i-1];
		g[u][i]=g[u][i-1]+g[fa[u][i-1]][i-1];
	}
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v,c=e[i].c;
		if(v==p) continue;
		fa[v][0]=u;g[v][0]=c;
		dfs(v,u);
		if(dep[v]+c>dep[u])
			dep[u]=dep[v]+c,son[u]=v;
	}
	for(int i=f[u];i;i=e[i].next)
		if(e[i].v^p && e[i].v^son[u])
			top[++k]=e[i].v,
			len[e[i].v]=dep[e[i].v]+e[i].c;
}
void init(int s)
{
	find(s,0);rt=s;
	for(int i=1;i<=n;i++)
		if(dep[i]>dep[rt]) rt=i;
	memset(dep,0,sizeof dep);
	dfs(rt,0);top[++k]=rt;len[rt]=dep[rt];
	sort(top+1,top+1+k,[&](int i,int j)
	{return len[i]>len[j];});
	for(int i=1;i<=k;i++)
		sum[i]=sum[i-1]+len[top[i]];
	for(int i=1;i<=k;i++)
	{
		int x=top[i];
		while(x) rnk[x]=i,x=son[x];
	}
}
int ask1(int x,int y)
{
	int res=dep[x];
	for(int i=19;i>=0;i--)
		if(rnk[fa[x][i]]>=y)
			res+=g[x][i],x=fa[x][i];
	return sum[y-1]+res+g[x][0];
}
int ask2(int x,int y)
{
	int res=dep[x];
	for(int i=19;i>=0;i--)
		if(rnk[fa[x][i]]>y)
			res+=g[x][i],x=fa[x][i];
	return sum[y]+res+g[x][0]-dep[fa[x][0]];
}
int qry(int x,int y)
{
	y=2*y-1;
	if(y>=k) return zxy;
	return rnk[x]<=y?sum[y]:
	max(ask1(x,y),ask2(x,y));
}

}T1,T2; 
signed main()
{
	n=read();m=read();
	for(int i=1;i