[CSP-S模拟测试]:Endless Fantasy（DFS）

题目描述

中二少年$cenbo$幻想自己统治着$Euphoric\ Field$。由此他开始了$Endless\ Fantasy$。
$Euphoric\ Field$有$n$座城市，$m$个民族。这些城市之间由$n-1$条道路连接形成了以城市$1$为根的有根树。每个城市都是某一民族的聚居地，$cenbo$知道第$i$个城市的民族是$A_i$，人数是$B_i$。为了维护稳定，$cenbo$需要知道某个区域内人数最多的民族。他向你提出$n$个询问，其中第$i$个询问是：求以$i$为根的子树内，人数最多的民族有是哪个，这个民族有多少人。如果子树内人数最多的民族有多个，输出其中编号最小的民族。

输入格式

第一行有两个整数$n,m$。
接下来$n-1$行，每行有两个整数$u,v$，表示一条连接$u$和$v$的道路。
接下来$n$行，第$i$行有两个整数$A_i,B_i$。

输出格式

第i行两个整数$x,y$，分别表示以$i$为根的子树中人数最多的民族和它的人数。

样例

样例输入：

8 6
1 2
1 3
2 4
4 5
3 6
5 7
1 8
2 8
2 5
1 1
3 1
6 7
5 6
1 10
4 6

样例输出：

2 13
1 10
5 6
1 10
1 10
5 6
1 10
4 6

数据范围与提示

$30\%$的数据，$n\leqslant 4,000$；
$60\%$的数据，$n\leqslant 40,000$；
$100\%$的数据，$n\leqslant 400,000$，$m\leqslant n$，$1\leqslant A_i\leqslant m$，$0\leqslant B_i\leqslant 1,000$。
输入文件较大请使用读入优化。

题解

不得不否认，这道题的确可以用线段树合并$A$掉。

但是我又没有打正解。

但是仔细观察，它是没有修改操作的，所以我们可以考虑另一种方法，先求出重儿子，然后暴力统计答案，理论上会被卡死。

时间复杂度：$\Theta($玄学$)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int nxt,to;}e[1000000];

int head[400001],cnt;

int n,m;

int a[400001],b[400001];

bool vis[400001];

int son[400001],size[400001];

int v[400001];

long long sum[400001];

pair<int,long long> ans[400001];

void add(int x,int y)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	head[x]=cnt;

}

void connect(int x)

{

	if(v[a[x]]!=sum[0])

	{

		v[a[x]]=sum[0];

		sum[a[x]]=b[x];

	}

	else sum[a[x]]+=b[x];

	if(sum[a[x]]>b[0])

	{

		a[0]=a[x];

		b[0]=sum[a[x]];

	}

	if(sum[a[x]]==b[0]&&a[x]<a[0])a[0]=a[x],b[0]=sum[a[x]];

}

void find(int x,int fa)

{

	connect(x);

	for(int i=head[x];i;i=e[i].nxt)

		if(e[i].to!=fa)find(e[i].to,x);

}

void pre_dfs(int x)

{

	vis[x]=1;

	size[x]=1;

	for(int i=head[x];i;i=e[i].nxt)

		if(!vis[e[i].to])

		{

			pre_dfs(e[i].to);

			size[x]+=size[e[i].to];

			if(size[e[i].to]>size[son[x]])son[x]=e[i].to;

		}

}

void pro_dfs(int x,int fa)

{

	if(!x)return;

	for(int i=head[x];i;i=e[i].nxt)

		if(e[i].to!=fa&&son[x]!=e[i].to)

		{

			pro_dfs(e[i].to,x);

			sum[0]++;

			b[0]=-1;

		}

	pro_dfs(son[x],x);

	for(int i=head[x];i;i=e[i].nxt)

		if(e[i].to!=fa&&son[x]!=e[i].to)

			find(e[i].to,x);

	connect(x);

	ans[x]=make_pair(a[0],b[0]);

}

int main()

{

	scanf("%d%d",&n,&m);

	sum[0]=1;b[0]=-1;

	for(int i=1;i<n;i++)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		add(x,y);add(y,x);

	}

	for(int i=1;i<=n;i++)

		scanf("%d%d",&a[i],&b[i]);

	pre_dfs(1);

	pro_dfs(1,0);

	for(int i=1;i<=n;i++)printf("%d %lld\n",ans[i].first,ans[i].second);

	return 0;

}

rp++

巴特西