[DS记录]CF526G Spiders Evil Plan
command_block
·
·
个人记录
题意 : 给定一棵 n 个点的无根树，每条边有边权。
有 q 次询问，每次给出 x,y ，需要选择 y 条树上的路径，使这些路径形成一个包含点 x 的连通块，且连通块中包含的边权和最大。
------------
先考虑单组询问。
- **定理** ： 树有不超过 $2k$ 个叶子 $\Leftrightarrow$ 可以被 $k$ 条路径覆盖。
必要性显然，下证充分性。
以叶子为权，选取重心为根，可以保证每个分支内部都有不超过 $k$ 个叶子。
将这些叶子匹配起来，让每条路径都经过根。
现在，对于每个叶子，其到根的路径都被覆盖过，显然整棵树都被覆盖了。
现在，以点 $x$ 为根，问题等价于选取 $2y$ 个叶子是的向上的路径并最大。(注意根也可能是叶子)
这等价于带权长剖后选择长度前 $2y$ (或者 $2y-1$ )的长链。
接下来考虑多组询问。
能够发现，无论以何点为根，最长的长链端点必然可以是直径的端点。也就是说，选出的树形图必然包含直径的端点之一。
所以，我们只需要考虑根为直径端点的情况。
选出前 $2y-1$ (直径端点必然是叶子) 的长链后，可能并不包含点 $x$，需要做些调整。
设 $x$ 子树内最深点为 $t$。
有如下两种方案 ：
- 去掉第 $2y-1$ 条长链，然后将 $t$ 到根的路径加入树形图。
- 找到 $t$ 被包含在树形图内的最深祖先，将所在长链的后半段切掉。
容易使用倍增实现。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 100500
using namespace std;
vector<int> g[MaxN],l[MaxN];
int n,dis[MaxN];
void pfs(int u)
{
for (int i=0,v;i<g[u].size();i++)
if (!dis[v=g[u][i]]){
dis[v]=dis[u]+l[u][i];
pfs(v);
}
}
struct Line{int u,v,len;};
bool cmpL(const Line &A,const Line &B)
{return A.len>B.len;}
struct Solver
{
int dis[MaxN],mp[MaxN],len[MaxN],f[20][MaxN];
void pfs1(int u)
{
for (int i=0,v;i<g[u].size();i++)
if (!dis[v=g[u][i]]){
f[0][v]=u;
dis[v]=dis[u]+l[u][i];
pfs1(v);
if (len[u]<len[v]+l[u][i])
len[u]=len[mp[u]=v]+l[u][i];
}
}
Line s[MaxN];
int tn,id[MaxN];
void pfs2(int u,int tf)
{
if (!mp[u]){
s[++tn]=(Line){tf,u,dis[u]-dis[tf]};
return ;
}
pfs2(mp[u],tf);
for (int i=0,v;i<g[u].size();i++)
if (dis[v=g[u][i]]>dis[u]&&v!=mp[u])
pfs2(v,u);
}
void Init(int rt)
{
dis[0]=dis[rt]=1;pfs1(rt);pfs2(rt,0);
sort(s+1,s+tn+1,cmpL);
for (int i=1;i<=tn;i++){
s[i].len+=s[i-1].len;
for (int p=s[i].v;p!=s[i].u;p=f[0][p])
id[p]=i;
}
for (int j=1;j<17;j++)
for (int i=1;i<=n;i++)
f[j][i]=f[j-1][f[j-1][i]];
}
int get(int u,int lim)
{
int k=17;
while(k--)
while(id[f[k][u]]>lim)
u=f[k][u];
return f[0][u];
}
int qry(int u,int c)
{
if (c>tn)return s[tn].len;
if (id[u]<=c)return s[c].len;
int ret=s[c-1].len+dis[u]+len[u]-dis[get(u,c-1)];
int t=get(u,c);
ret=max(ret,s[c].len+dis[u]+len[u]-dis[s[id[t]].v]);
return ret;
}
}T1,T2;
int q;
int main()
{
scanf("%d%d",&n,&q);
for (int i=1,u,v,c;i<n;i++){
scanf("%d%d%d",&u,&v,&c);
g[u].pb(v);l[u].pb(c);
g[v].pb(u);l[v].pb(c);
}
int tp=1;
dis[1]=1;pfs(1);
for (int i=1;i<=n;i++)
if (dis[i]>dis[tp])tp=i;
T1.Init(tp);
for (int i=1;i<=n;i++)dis[i]=0;
dis[tp]=1;pfs(tp);
for (int i=1;i<=n;i++)
if (dis[i]>dis[tp])tp=i;
T2.Init(tp);
for (int i=1,u,c,las=0;i<=q;i++){
scanf("%d%d",&u,&c);
u=(u+las-1)%n+1;
c=(c+las-1)%n+1;
c=c*2-1;
printf("%d\n",las=max(T1.qry(u,c),T2.qry(u,c)));
}return 0;
}
```