作者:啊123 | 来源:互联网 | 2023-09-16 09:45
题意:
给定n个点的带边权树Q个询问。
下面n-1行给出树
下面Q行每行一个数字表示询问。
首先求出dp[N] :dp[i]表示i点距离树上最远点的距离
询问u, 表示求出 dp 数组中最长的连续序列使得序列中最大值-最小值 <= u,输出这个序列的长度。
思路:
求dp数组就是求个树的直径然后dfs一下。
对于每个询问,可以用一个单调队列维护一下。O(n)的回答。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
template
inline bool rd(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if(x>9) pt(x/10);
putchar(x%10+'0');
}
typedef long long ll;
const int N = 50010;
int n, Q;
struct Edge{
int to, nex; ll dis;
}edge[N<<1];
struct node {
int v, id;
node() {}
node(int _id, int _v) {
id = _id; v = _v;
}
};
int head[N], edgenum;
void init(){for(int i = 1; i <= n; i++)head[i] = -1; edgenum = 0;}
void add(int u, int v, ll d){
Edge E = {v, head[u], d};
edge[edgenum] = E;
head[u] = edgenum++;
}
ll dis[N], dp[N], len;
int Stack[N], top, pre[N], vis[N];
int BFS(int x){
for(int i = 1; i <= n; i++)
dis[i] = -1;
dis[x] = 0; pre[x] = -1;
int far = x;
queue q; q.push(x);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = edge[i].nex){
int v = edge[i].to;
if(dis[v] == -1)
{
dis[v] = dis[u] + edge[i].dis;
pre[v] = u;
if(dis[far] >n>>Q, n+Q) {
input();
build();
while(Q--)
{
rd(v);
ans = h1 = t1 = h2 = t2 = 0;
idx = 1;
for (int i = 1; i <= n; ++i) {
while (h1!=t1 && mx[t1-1].v <= dp[i])
-- t1;
mx[t1++] = node(i, dp[i]);
while (h2!=t2 && mi[t2-1].v >= dp[i])
-- t2;
mi[t2++] = node(i, dp[i]);
while (h1!=t1&&h2!=t2) {
if (mx[h1].v-mi[h2].v>v)
++ idx;
else
break;
while (h1!=t1&&mx[h1].id