洛谷 P7043 「MCOI-03」村国

题目背景

What did this player dream? exttt{What did this player dream?}What did this player dream?

他梦见了什么？

This player dreamed of sunlight and trees.Of fire and water. exttt{This player dreamed of sunlight and trees.Of fire and water.}This player dreamed of sunlight and trees.Of fire and water.

他梦见了阳光与树木。梦见了火与水。

It dreamed it created. And it dreamed it destroyed. It dreamed it hunted, exttt{It dreamed it created. And it dreamed it destroyed. It dreamed it hunted,}It dreamed it created. And it dreamed it destroyed. It dreamed it hunted, and was hunted. It dreamed of shelter. exttt{and was hunted. It dreamed of shelter.}and was hunted. It dreamed of shelter.

他梦见他的创造，亦梦见他毁灭。它梦见他在狩猎，亦梦见被猎捕。他梦见温馨的居所。

Hah, the original interface. A million years old, and it still works.But exttt{Hah, the original interface. A million years old, and it still works.But}Hah, the original interface. A million years old, and it still works.But what true structure did this player create, in the reality behind the screen? exttt{ what true structure did this player create, in the reality behind the screen?} what true structure did this player create, in the reality behind the screen?

哎，那原始的界面。经历百万年的岁月，它依然在工作。只是他在屏幕后的真实里，到底创造了什么真实的世界呢？

题目描述

C 国一共有 NNN 个村庄，N−1N-1N−1 条道路。这些道路都可以双向通行。保证小 S 可以从一座村庄到其他任何一座村庄。这 NNN 个村庄编号为 111 到 NNN。

刚开始小 S 对第 iii 个村庄的好感值为 AiA_iAi。小 S 的假期一共有 MMM 天，他会在 C 国旅行一共 MMM 天。每一天他会选择来到当前好感值最高的村庄。如果有好感值相同的村庄，他会选择编号最小的村庄。假设这一天他来到村庄 XXX，那么这一天结束后，与村庄 XXX 直接相邻所有村庄的好感值都会增加 111。即能从 XXX 出发仅经过一条道路到达的村庄好感值会增加 111。因为小 S 已经在村庄 XXX 待过一天了，所以这一天结束后村庄 XXX 的好感值并不会增加。

现在小 S 想要知道经过 MMM 天的旅行后好感值最高的村庄。

如果有多个好感值最高的村庄，输出编号最小的。

输入格式

本题单个测试点包含多组测试数据。
第一行一个正整数 TTT 表示数据组数。
对于每组数据：
第一行包括两个正整数 N,MN,MN,M，表示村庄个数和旅行天数。
接下来一行 NNN 个整数，第 iii 个整数表示第 iii 座村庄的好感值 AiA_iAi。
接下来 N−1N-1N−1 行。每行两个整数 x,yx,yx,y 表示村庄 xxx 和村庄 yyy 之间有一条双向通行的道路。

输出格式

一个整数表示 MMM 天结束后好感值最高的村庄的编号。如果有多个好感值最高的村庄，输出编号最小的。

题解：

一开始看这道题感到还是很棘手的，至少不那么一眼切。后来看到M是10的18.觉得是一道找规律的题，否则不可做。

于是尝试着找规律。

发现，对于第一次选择的点，也就是最大权值的最小编号点，这M天只可能在这个点和与这个点相连的最大权值最小编号点上。

这个结论手画就能证明。

于是我们模拟他住宿的过程。

发现先填满差值，然后再一左一右。

注意分编号相对大小来讨论。

就可以。

非常让人迷惑的是，链式前向星+手动记录就可以AC。我一开始用的vector存图+优先队列就WA四个点。有大佬教教为什么呢？

代码：

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=getchar();
   	return x*f;
}
const int maxn=2*1e6+3;
const int INF=1e9;
int n,m;
int w[maxn];
int tot,head[maxn],nxt[maxn<<1],to[maxn<<1];
void clear()
{
	memset(head,0,sizeof(head));
	memset(nxt,0,sizeof(nxt));
	memset(to,0,sizeof(to));
	tot=0;
	memset(w,0,sizeof(w));
}
void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
signed main()
{
	int t;
	t=read();
	while(t--)
	{
		clear();
		n=read();m=read();
		int mid=0;
		for(int i=1;i<=n;i++)
		{
			w[i]=read();
			if(w[i]>w[mid])
				mid=i;
		}
		for(int i=1;i<n;i++)
		{
			int x,y;
			x=read();y=read();
			add(x,y);
			add(y,x);
		}
		if(n==1)
		{
			puts("1");
			continue;
		}
		int now=0;//now为当前枚举到的次大权值。
		int dist=0;//dist为最大权值和次大权值的差值
		int y=INF;//y为与x相连的最大权值点编号。
		for(int i=head[mid];i;i=nxt[i])
		{
			int v=to[i];
			if(w[v]>=now)
			{
				now=w[v];
				y=min(y,v);
				dist=w[mid]-now;
			}
		}
		if((m-dist)<0)
		{
			printf("%lld
",mid);
			continue;
		}
		int maxx=max(mid,y);
		int minn=min(mid,y);
		if((m-dist)&1)//奇数
		{
			printf("%lld
",maxx);
			continue;
		}
		if(!((m-dist)&1))
		{
			printf("%lld
",minn);
			continue;
		}
	}
	return 0;
}