计算机网络技术网站建设方向,建设网站专业公司哪家好,重庆新闻论坛新闻评论,网站后期维修问题正题
题目链接:https://www.luogu.com.cn/problem/CF516D 题目大意
给出一棵nnn个点的树#xff0c;定义f(x)f(x)f(x)表示距离点xxx最远的点的距离#xff0c;qqq次询问给出一个kkk#xff0c;要求一个最大的连通块满足连通块中所有点的f(x)f(x)f(x)最大最小差值不能超过k…正题
题目链接:https://www.luogu.com.cn/problem/CF516D 题目大意
给出一棵nnn个点的树定义f(x)f(x)f(x)表示距离点xxx最远的点的距离qqq次询问给出一个kkk要求一个最大的连通块满足连通块中所有点的f(x)f(x)f(x)最大最小差值不能超过kkk。
1≤n≤105,1≤q≤501\leq n\leq 10^5,1\leq q\leq 501≤n≤105,1≤q≤50 解题思路
我们找到f(x)f(x)f(x)最小的点作为根那么肯定有每一个点的f(x)f(x)f(x)都不小于其父节点的具体原理是因为每个点出发的最长简单路端点肯定是直径的某一端而这个最小的f(x)f(x)f(x)可以视为直径的中点。
那么对于每个询问我们就直接枚举所有点然后往上倍增到一个深度最浅的祖先满足f(x)−f(z)≤kf(x)-f(z)\leq kf(x)−f(z)≤k然后用树上差分给z↔xz\leftrightarrow xz↔x路径上所有点的权值111最后求一个点权最大的点就好了。
时间复杂度O(qnlogn)O(qn\log n)O(qnlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
struct node{ll to,next,w;
}a[N1];
ll n,q,tot,rt,ls[N],len[N];
ll f[N][18],dep[N],c[N];
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(ll x,ll fa){for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);len[x]max(len[x],len[y]a[i].w);}return;
}
void calc(ll x,ll fa,ll mxl){ll mxmxl,mi0;len[x]max(len[x],mxl);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;if(mxlen[y]a[i].w)mimx,mxlen[y]a[i].w;else if(milen[y]a[i].w)milen[y]a[i].w;}for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;if(mxlen[y]a[i].w)calc(y,x,mia[i].w);else calc(y,x,mxa[i].w);}return;
}
void sfd(ll x,ll fa){dep[x]dep[fa]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;f[y][0]x;sfd(y,x);}return;
}
void carc(ll x,ll fa){for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;carc(y,x);c[x]c[y];}return;
}
void Query(ll d){memset(c,0,sizeof(c));len[0]-1e18;for(ll i1;in;i){ll xi;for(ll j17;j0;j--)if(len[i]-len[f[x][j]]d)xf[x][j];c[i];c[f[x][0]]--;}carc(rt,0);ll ans0;for(ll i1;in;i)ansmax(ans,c[i]);printf(%lld\n,ans);return;
}
signed main()
{scanf(%lld,n);for(ll i1,x,y,w;in;i){scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);}dfs(1,0);calc(1,0,0);len[0]1e18;for(ll i1;in;i)if(len[i]len[rt])rti;sfd(rt,0);for(int j1;j18;j)for(int i1;in;i)f[i][j]f[f[i][j-1]][j-1];scanf(%lld,q);while(q--){ll x;scanf(%lld,x);Query(x);}return 0;
}
