查企业网站,合肥今天的最新消息,安徽省建设项目 备案网站,怎么做提取微信62的网站Description
一棵 n 个结点的树#xff0c;有正边权。 用 y 条链覆盖这棵树#xff0c;满足#xff1a;
所有链连通#xff08;有重点即算作相连#xff09;点 x 被覆盖被覆盖的边的权值和尽可能大 q 次给出 x, y#xff0c;询问最大边权和#xff0c;强制在线。 n, q…Description
一棵 n 个结点的树有正边权。 用 y 条链覆盖这棵树满足
所有链连通有重点即算作相连点 x 被覆盖被覆盖的边的权值和尽可能大 q 次给出 x, y询问最大边权和强制在线。 n, q ≤ 10510^5105
Solution
可以发现一些比较显然的性质
权值是正的那么链的端点一定可以全部调整成叶子。如果链不连通可以交换链的端点使它们连通。使用 k 条路径就可以覆盖一棵有 2k 个叶子的树。先以任意方式匹配叶子。如果有两条路径不相交可以调整成相交的情况。 不断调整就可以让任意两条路径都相交于是显然覆盖了整棵树。
现在问题是寻找 2 ∗ y 个叶子使 x 被包含使被包含的边权和最大。考虑单次询问怎么办。如果只有一次询问我们就把询问的点 x 提作根如果 x 的度数不为 1 那么选 y 条路径的最优方案必然可以转化为选 2y 个叶子然后求这 2y 个叶子到 x 的路径的并的长度。如果 x 的度数为 1 的话那么就是选 2y-1 个叶子因为有一条路径要从 x 出发。那么显然就可以贪心的选当前贡献最大的叶子加入答案了。如果有多组询问呢每次询问都换根显然不现实但发现每次询问中一定存在一种方案使得直径的两端中至少有一端被选取。那我们就可以把直径的两个端点分别作为根来考虑最后询问的时候取最大值即可。考虑对每棵树预处理出 ansians_iansi 表示当前选了 i 个叶子的最大权值和这个可以用 DFS序的线段树或者是长链剖分来实现。
线段树实现每个叶子节点的贡献是 它的深度-它到根路径上已经被其它路径覆盖的部分的长度用线段树维护一下叶子的贡献每次贪心的选取贡献最大的叶子长链剖分实现一个子树内最先被选的显然是深度最大的叶子那么一个叶子的贡献就是在长链剖分后所在重链以及上方第一条轻边的距离。
然后考虑一次询问 x,y。如果 ans2y−1ans_{2y-1}ans2y−1中包含了 x 点那么直接输出 ans2y−1ans_{2y-1}ans2y−1即可。否则加入 x 子树内最深叶子然后需要删去一个之前选的叶子使得减少的权值最小
这个叶子可能是最后一个被选的叶子也就是贡献最小的那个。由于 x 的加入与 x 的 lca 最深的被选叶子的贡献可能会减小而被删去。找离 x 最近的有叶子被选的祖先的一条路径砍掉一半后跟 x 的子树中深度最大的点接上。
可以发现第一种情况好办倍增跳到到第一个被访问时间 ≤2y−2\leq 2y-2≤2y−2 祖先 u 那么答案就是 ans2y−2−dep[u]mx[x]ans_{2y-2}-dep[u]mx[x]ans2y−2−dep[u]mx[x]。然后考虑第二种情况。第二种情况乍一看需要维护在所有时间所有点的子树内选的叶子节点的权值的最小值这个很麻烦。但是仔细想想可以发现只有在这个祖先的子树内只有一个叶子节点被选的时候这种情况才可能有第一种情况优。因为如果多于两个叶子那么删掉最小的那个叶子节点所减去的依旧是这个点加进来时候的权值既然是减去加进来的权值那么第一种情况显然是最小的。如果只有一个叶子那么这个叶子所代表的链跟 x 到根的路径是有交的所以才有可能更短。实现方面可以倍增跳到第一个被访问时间 ≤2y−1\leq 2y-1≤2y−1的节点 u那么答案就会是 ans2y−1−mx[u]mx[x]ans_{2y-1}-mx[u]mx[x]ans2y−1−mx[u]mx[x]。那么最终的答案就是两颗树的两种情况的最大值了。时间复杂度 O((nq)logn)O((nq)\log n)O((nq)logn)。 疑问就网上的其它博客和我自己的提交来看直径两端点分别作为根的情况好像不用都考虑随便找一种就好。这样做为什么是对的知道的朋友可以麻烦解答一下吗
Code
#includeiostream
#includecstdio
using namespace std;
const int N1e55;
struct Edge{int v,w,nxt;
}edge[N1];
int n,m,head[N],cnt,rt,mxd,lstans,ans[N];
int fa[N][25],dep[N],son[N],dfn[N],ind,ln[N],md[N],low[N];
pairint,int mx[N2];int tag[N2];
int vis[N];
void add(int u,int v,int w){edge[cnt].vv;edge[cnt].ww;edge[cnt].nxthead[u];head[u]cnt;
}
void find(int u,int f,int d){if(dmxd){rtu;mxdd;} for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vf) continue;find(v,u,dedge[i].w);}
}
void dfs(int u,int f){ln[dfn[u]ind]u;md[u]dep[u];for(int i1;i20;i){if(!fa[fa[u][i-1]][i-1]) break;fa[u][i]fa[fa[u][i-1]][i-1];}for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vf) continue;dep[v]dep[u]edge[i].w;fa[v][0]u;dfs(v,u);md[u]max(md[u],md[v]);}low[u]ind;
}
void pushup(int u){if(mx[u1].firstmx[u1|1].first) mx[u]mx[u1|1];else mx[u]mx[u1];
}
void build(int u,int l,int r){if(lr){mx[u]make_pair(dep[ln[l]],ln[l]);return;}int mid(lr)1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);
}
void pushdown(int u,int l,int r){if(tag[u]){mx[u1].firsttag[u];mx[u1|1].firsttag[u];tag[u1]tag[u];tag[u1|1]tag[u];tag[u]0;}
}
void update(int u,int l,int r,int a,int b,int w){if(alrb){mx[u].firstw;tag[u]w;return;}pushdown(u,l,r);int mid(lr)1;if(amid) update(u1,l,mid,a,b,w);if(bmid) update(u1|1,mid1,r,a,b,w);pushup(u);
}
void prework(){dfs(rt,0);build(1,1,n);//贪心每次选取贡献最大的点,选完后修改其它点的贡献 for(int i2;in;i){ans[i]ans[i-1]mx[1].first;for(int jmx[1].second;j!vis[j];jfa[j][0]){vis[j]i;update(1,1,n,dfn[j],low[j],dep[fa[j][0]]-dep[j]);}}
}
int solve(int x,int y){ymin(y,n);if(vis[x]y) return ans[y];//x已经被覆盖int ux;for(int i20;i0;i--)if(vis[fa[x][i]]y) xfa[x][i];xfa[x][0];return ans[y]md[u]-dep[x]-min(dep[x],min(ans[y]-ans[y-1],md[x]-dep[x]));
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){int u,v,w;scanf(%d%d%d,u,v,w);add(u,v,w);add(v,u,w);}find(1,0,0);//找直径端点 prework();for(int i1;im;i){int u,v;scanf(%d%d,u,v);u(ulstans-1)%n1;v(vlstans-1)%n1;printf(%d\n,lstanssolve(u,v1));}return 0;
}参考文章 https://www.luogu.com.cn/blog/46396/solution-cf526g
