C/C++教程

BalticOI2017 Railway

本文主要是介绍BalticOI2017 Railway，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

看了一眼网上的题解，好像我的做法没有出现（？），并且我的做法好像比较简单易懂（？），不用虚树也不用线段树维护

不难想到，我们可以对于每个副部长的点连成的最短路径（即这个路径里的每条边都是必要的）上+1，然后看有哪些路是\(>=k\)的，但是我们需要不重复不遗漏的把这个路径都走到。于是我们考虑把这些点树链剖分，按照树剖的顺序排个序，因为我们走路径一定是要按照某种顺序的，可以想象成，把一条链抽出来，两点距离就是最短距离（感性理解一下），然后每次对相邻接点进行树上差分，即当前点++，lca--，就行了，但是要注意的是，他们这些点的 lca 是要放在最后单独处理一下的

最后dfs求子树和，统计一下答案就行了

点击查看代码 
//CAN'T FORGET
//CAN'T FORGET
//CAN'T FORGET

//#pragma GCC optimize("Ofst")
#include<bits/stdc++.h>
using namespace std;
#define _ 0
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
struct node{
	int to,nxt;
}edge[maxn];
int head[maxn],tot;
void addedge(int u,int v)
{
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
int sz[maxn],dep[maxn],f[maxn],son[maxn];
int top[maxn];
void dfs1(int x,int fa)
{
	sz[x]=1;
	dep[x]=dep[fa]+1;
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int y=edge[i].to;
		if(y==fa)
			continue;
		f[y]=x;
		dfs1(y,x);
		sz[x]+=sz[y];
		if(sz[son[x]]<sz[y])
			son[x]=y;
	}
}
int dfn[maxn],id;
void dfs2(int x,int tp)
{
	dfn[x]=++id;
	top[x]=tp;
	if(son[x]!=0)
		dfs2(son[x],tp);
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int y=edge[i].to;
		if(y==f[x]||y==son[x])
			continue;
		dfs2(y,y);
	}
}
int getlca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>=dep[top[v]])
			u=f[top[u]];
		else
			v=f[top[v]];
	}
	if(dep[u]<dep[v])
		return u;
	return v;
}
int sum[maxn],ans[maxn],nm;
void dfs3(int x,int fa)
{
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int y=edge[i].to;
		if(y==fa)
			continue;
		dfs3(y,x);
		sum[x]+=sum[y];
	}
}
int s[maxn],x[maxn];
map<pair<int,int>,int> dy;
bool cmp(int a,int b)
{
	return dfn[a]<dfn[b];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n-1;i++)
    {
    	int u,v;
    	cin>>u>>v;
    	addedge(u,v);
    	addedge(v,u);
    	dy[make_pair(u,v)]=i;
    	dy[make_pair(v,u)]=i;
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		cin>>s[i];
		for(int j=1;j<=s[i];j++)
			cin>>x[j];
		sort(x+1,x+s[i]+1,cmp);

		sum[x[1]]++;
		int lca=x[1];
		for(int j=2;j<=s[i];j++)
		{
			sum[x[j]]++;
			int lc=getlca(x[j-1],x[j]);
			sum[lc]--;
			lca=getlca(lca,x[j]);
		}
		sum[lca]--;
	}
	dfs3(1,0);
	for(int i=2;i<=n;i++)
		if(sum[i]>=k)
			ans[++nm]=dy[make_pair(f[i],i)];
	sort(ans+1,ans+nm+1);
	cout<<nm<<endl;
	for(int i=1;i<=nm;i++)
		cout<<ans[i]<<" ";
	cout<<endl;
	return ~~(0^_^0);
}
/*
Notes:
1.看所有题目
2.注意数据范围
3.想想自己还能做什么而不是做了什么
4.看清题目!!!
5.记得把调试代码删掉!!!!
6.longlong时 1要写成1ll
7.Think twice code once, think once code forever!
*/
这篇关于BalticOI2017 Railway的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航