推广网站怎么做知乎,品牌网站建设价格实惠,网站建设上海网站建设公司网站,深圳企业注销一窗通长剖的本质是一种贪心。#xff08;启发式合并本质也是类似哈夫曼树的过程#xff09;
在此题中#xff0c;首先肯定变直径#xff0c;然后选端点为根。然后选叶子。而每个叶子为了不重复计算#xff0c;可以只计算其长剖后所在链的贡献。#xff08;本题精髓#xff0…长剖的本质是一种贪心。启发式合并本质也是类似哈夫曼树的过程
在此题中首先肯定变直径然后选端点为根。然后选叶子。而每个叶子为了不重复计算可以只计算其长剖后所在链的贡献。本题精髓用长剖来贪心
然后钦定某个点必选就是一种反悔贪心。很显然的思路是删掉排名 2 ∗ k − 1 2*k-1 2∗k−1 的叶子但考虑 所以需要考虑离其最近被选的点 #includebits/stdc.h
using namespace std;
//#define int long long
inline int read(){int x0,f1;char chgetchar(); while(ch0||
ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){
x(x1)(x3)(ch^48);chgetchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 500010
//#define M
//#define mo
struct node { int x; long long y, z; };
int n, m, i, j, k, T, p1, p2, in[N];
int u, v, w, qe;
vectornodeG[N]; struct Tree {int i, j, k, rt, mn[N]; long long h[N], mxh[N], mx[N], sum[N]; int son[N], dep[N], top[N]; int f[N][22], rk[N], dfn[N]; node w[N]; void dfs1(int x, int fa, int p1) {//p1 p2if(h[x]h[p1]) p1x; for(auto t : G[x]) {int yt.y; long long zt.z; if(yfa) continue; h[y]h[x]z; dfs1(y, x, p1); }}void dfs2(int x, int fa) { //son[x] h[x] dep[x]dep[x]dep[fa]1; mx[x]mxh[x]h[x]; for(auto t : G[x]) {int yt.y; long long zt.z; if(yfa) continue; h[y]h[x]z;
// printf(%lld(%lld) --%lld- %lld(%lld)\n, x, h[x], z, y, h[y]); dfs2(y, x); mx[x]max(mx[x], mx[y]); if(mxh[y]mxh[son[x]]) son[x]y; }if(son[x]) mxh[x]mxh[son[x]]; }void dfs3(int x, int fa, int tp) {//top[x] w[x]
// printf( %d\n, tp); top[x]tp; f[x][0]fa; if(in[x]1 fa) {w[x].yh[x]-h[f[top[x]][0]]; w[x].xx; }for(auto t : G[x]) {int yt.y; if(yfa) continue; if(yson[x]) dfs3(y, x, tp); else dfs3(y, x, y); }}void init() {
// for(i1; in; i) printf(%d , top[i]); printf(\n);
// for(i1; in; i) printf(%d , h[i]); printf(\n); sort(w1, wn1, [] (node x, node y) { return x.yy.y; }) ; reverse(w1, wn1); for(i1; in; i) {
// printf(%lld(%lld) , w[i].y, w[i].x); if(w[i].x) sum[i]w[i].y, rk[w[i].x]i, dfn[i]w[i].x; sum[i]sum[i-1]; }
// printf(\n); for(k1; k19; k) for(i1; in; i) f[i][k]f[f[i][k-1]][k-1]; }void dfs4(int x, int fa) {if(in[x]1 fa) mn[x]rk[x]; else mn[x]1e9; for(auto t : G[x]) {int yt.y, zt.z; if(yfa) continue; dfs4(y, x); mn[x]min(mn[x], mn[y]); //排名最小 }}int tiao(int x, int g) {for(k19; k0; --k)if(mn[f[x][k]]g) xf[x][k]; return f[x][0]; }int lca(int x, int y) {if(xy) return x; if(dep[x]dep[y]) swap(x, y); for(int k19; k0; --k)if(dep[f[x][k]]dep[y]) xf[x][k]; if(xy) return x; for(int k19; k0; --k)if(f[x][k]!f[y][k]) xf[x][k], yf[y][k]; return f[x][0]; }long long calc(int y, int oldy, int newx) {
// printf(Lca(%d %d) : %d\n, oldy, newx, lca(oldy, newx));
// return min(w[mn[y]].y, h[oldy]-h[lca(oldy, newx)]); return min(w[mn[y]].y, h[oldy]-h[y]); }long long que(int x, int k) {if(k1) {
// int ydfn[mn[x]]; return h[y]; return mx[x]; }if(mn[x]2*k-1) {return sum[min(2*k-1, n)]; }int ytiao(x, 2*k-1), newx, oldy; long long ans; newxdfn[mn[x]]; oldydfn[mn[y]];
// printf(%d | %d %d %d %d\n, y, newx, oldy, (h[newx]-h[y]), calc(y, oldy, newx)); anssum[2*k-1]-calc(y, oldy, newx)(h[newx]-h[y]); ansmax(ans, sum[2*k-1]-w[2*k-1].y(h[newx]-h[y])); return ans; }
}T1, T2;void print(long long x) {if(x) print(x/10), putchar(x%100);
}signed main()
{
// freopen(in.txt, r, stdin);
// freopen(out.txt, w, stdout);freopen(bomb.in, r, stdin);freopen(bomb.out, w, stdout);
// Tread();
// while(T--) {
//
// }nread(); qeread(); for(i1; in; i) {uread(); vread(); wread(); G[u].pb({u, v, w}); G[v].pb({v, u, w}); in[u]; in[v]; }T1.h[1]0; T1.dfs1(1, 0, p1); T1.h[p1]0; T1.dfs1(p1, 0, p2);T1.rtp1; T2.rtp2; T1.h[p1]0; T1.dfs2(p1, 0); T2.h[p2]0; T2.dfs2(p2, 0);
// printf(%d %d\n, p1, p2); T1.dfs3(p1, 0, p1); T2.dfs3(p2, 0, p2); T1.init(); T2.init(); T1.dfs4(p1, 0); T2.dfs4(p2, 0); while(qe--) {uread(); kread(); print(max(T1.que(u, k), T2.que(u, k))); puts(); }return 0;
}
