夏晓光(loveJY)的博客

IOI2020集训队作业

不扯那些玄乎的直接看题

题目描述：一棵$n$个点的树，设$d(u)=\max_{v\in V}\text{dis}(u,v)$，每次询问一个数$l$，求一个最大的联通子图$L$，使得$\forall u,v\in L,|d(u)-d(v)|\leq l$;输出$|L|$.

数据范围：$n\leq 10^5,w\leq 10^6,l\leq 10^{11},q\leq 50$

首先我们有个很直接的想法是求出树的直径,因为这样就能快速求出d值了

其实单求dis值就是普及难度吧

然后我们再考虑q这么小,一定是$O(n)$一组

再加上最大减去最小能联想到什么?莫队?但$O(n)$一组?尺取!

但是不能瞎尺取,我们再利用一下d的性质

仔细一想:dis值从直径中点开始向四周递减!

那么有了这个就可以保证以中点为根,从根到叶子的dis值递增

就意味着如果我们把点权排个序,然后在上面用区间尺取,从maxdis向外弹出,相当于从连通块中删除叶子,就能保证我们尺取的区间覆盖答案的连通块

怎么快速判断尺取的区间连通块?这是并查集问题

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=BUF_SIZE+buf,*pend=BUF_SIZE+buf;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline ll read() {
		ll x=0,f=1;
		register char s=nc();
		for(; !isdigit(s); s=nc())if(s=='-')f=-1;
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x*f;
	}
}
using namespace fastIO;

const int MAXN=1e5+7;
int n,ans;
struct rec {
	int to,nxt,w;
} e[MAXN*2];
int home[MAXN],tot,rt,fa[MAXN],p[MAXN],siz[MAXN],vis[MAXN];
ll dis[MAXN],d[MAXN];

inline void add(int w,int u,int v) {
	e[++tot]=(rec) {
		v,home[u],w
	};
	home[u]=tot;
	e[++tot]=(rec) {
		u,home[v],w
	};
	home[v]=tot;
}

void dfs(int u,int fa) {
	d[u]=max(d[u],dis[u]);
	if(dis[u]>dis[rt])rt=u;
	for(int i=home[u]; i; i=e[i].nxt) {
		int v=e[i].to;
		if(v!=fa)dis[v]=dis[u]+e[i].w,dfs(v,u);
	}//这里做一下dp,找到距离最远者
}

int find(int x) {
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}

void merge(int x,int y) {
	x=find(x);
	y=find(y);
	if(x==y)return ;
	if(siz[y]>siz[x])swap(x,y);
	siz[x]+=siz[y];//启发式合并
	ans=max(ans,siz[x]);
	fa[y]=x;
}

bool cmp(const int &a, const int &b) {
	return d[a]<d[b];
}

int main() {
//	freopen("test.in","r",stdin);
	n=read();
	for(int i=1; i<n; ++i)add(read(),read(),read());
	dfs(1,0);
	int tmp=rt;
	dis[rt]=0;
	rt=0;
	dfs(tmp,0);//找 到 直 径
	//并完成d
	dis[rt] =0;
	dfs(rt,0);

	for(int i=1; i<=n; ++i)p[i]=i;
	sort(p+1,p+n+1,cmp);
	//把点按照d值排序
	int q=read();
	ll lim;
	while(q-->0) {
		lim=read();
		for(int i=1; i<=n; ++i)fa[i]=i,siz[i]=1,vis[i]=0;
		//init
		ans=1;
		for(int k=n,j=n; k>=1; --k) {
			while(d[p[j]]>d[p[k]]+lim) {
				//j这个点不行
				//弹出来
				--siz[find(p[j])];
				--j;
				//换下一个的啦
			}
			vis[p[k]]=1;
			//相当于我们左端点靠枚举,右端点尺取
			for(int i=home[p[k]]; i; i=e[i].nxt) {
				int v=e[i].to;
				if(vis[v])merge(p[k],v);
				//merge一下表示那些点都归我管
				//主要是为了ans的更新---取最大连通块
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}