NKOJ 3489 避难向导（LCA+倍增+DFS/DP）

发表于 |
字数统计: 1,961字 | 阅读时长 ≈ 9min

P3489【2015多校联训5】避难向导

问题描述

“特大新闻，特大新闻！全国爆发了一种极其可怕的病毒，已经开始在各个城市中传播开来！全国陷入了巨大的危机！大量居民陷入恐慌，想要逃到其它城市以避难！经调查显示，该病毒来自于C 市的A 学校的一次非法的……”
“哎。”你关上电视，叹了口气。作为A 学校的校长，你一天前为了保命，独自逃离了A 学校，抛弃了全校师生，包括那个曾经帮你计算并拆除道路的工程师。
你良心受到了巨大的谴责，因此决定做出一些补救，回答一些逃难的人提出的询问。
已知该国一共有n 个城市，并且1 号城市是首都。(n-1)条双向的公路连接这些城市，通过这些公路，任意两个城市之间存在且仅存在一条路径。每条公路有一个长度。如果一个城市只与一条公路相连，则称它为边境城市。
该国政府有一个奇怪的规定：每个城市有一个封闭系数di，定义di 为离这个城市最远的边境城市到这个城市的距离。市民们认为，一个城市的安全系数Si 和它的封闭系数有很重要的联系。a，b，c 是该国的幸运数字，所以大家公认一个城市的安全系数Si = (di + a) * b mod c。
市民们一共会提出m 次询问。每个询问包含三个信息，xi，yi 和qi。xi 是询问者所在的城市编号。你要为这个询问者在xi 到yi 的必经之路上找出一个离xi最近的避难城市，并且要求这个避难城市的安全系数大于等于qi。如果存在这样的城市（包含xi 和yi），则输出城市编号，否则输出一行包括一个数-1。

输入格式

第一行五个数：依次是n, m, a, b, c。
接下来n-1 行描述公路的信息。每行三个数，前两个数代表这条公路连接的两个城市的编号，第三个数表示这条公路的长度。
再接下来m 行，每行描述一个询问，包含三个数xi, yi 和qi。

输出格式

对于每个询问，输出一行包含一个整数，存在符合要求的城市则输出城市编号，不存在则输出-1。

样例输入

7 6 5 6 20
1 2 4
2 4 2
2 5 3
1 3 5
3 6 6
6 7 7
7 5 15
3 4 5
5 4 2
4 5 2
6 6 10
3 5 19

样例输出

6
3
2
4
6
-1

数据范围

对于100%数据, 0 < xi, yi<=n; a,b,c,qi<=1,000,000;
注意：计算安全系数的中间过程可能需要使用64 位整数。

首先求安全系数，那么显然是找一条直径，然后到直径的某一个端点一定是最远距离，然而我居然写了个恶心的树dp

然后询问一条路径上，离起点最近的且安全系数大于$qi$的点，那么暴力枚举，$n^2$，显然不行，需要优化。

考虑倍增，$Maxdis[i][k]$表示$i$号节点的父亲开始往上$2^k$个节点中，最大的安全系数，显然很好预处理。

查找时先找出$x$和$y$的$lca$，先考虑$x$到$lca$这一段路径上的点。

此时直接倍增处理，从大到小枚举$k$，由于找与$x$最接近的，那么如果$Maxdis[x][k]<qi$，$x=father[x][k]$，否则缩小$k$，注意端点很容易找到答案。

然后考虑$x$到$lca$没找到时，查找$lca$到$y$，此时需要找与$y$最远的一个点，上面的方法就行不通了。

此时可以暴力一点，每次枚举到$k$时，如果$Maxdis[x][k]>=qi$那么先递归查询$father[x][k-1]$到$father[x][k]$这一段区间，如果找到了就直接返回，否则再查找$x$到$father[x][k-1]$，如果$Maxdis[x][k]<qi$，那么直接缩小$k$，时间复杂度比较玄学，出题人说是$O(nlogn)$的，那就这样吧。
还有另外一种处理方法，只需要二分答案枚举一下答案点的位置，然后验证是否找得到就行了。复杂度$O(nlog^2n)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 100005
#define M 200005
using namespace std;
ll n,m,S=20,cnt;
ll TOT,LA[N],NE[M],EN[M],LE[M];
ll V[N],Fdis[N],Mdis[N],MSdis[N],dis[N][22],a,b,c;
ll F[N][22],dep[N],MS[N];
void ADD(ll x,ll y,ll z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
ll DFS1(ll x,ll f)
{
	ll maxdis=0,id=0,i,y,tmp;
	F[x][0]=f;
	dep[x]=dep[f]+1;
	for(i=1;i<=S;i++)F[x][i]=F[F[x][i-1]][i-1];
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)
		{
			tmp=DFS1(y,x)+LE[i];
			if(tmp>maxdis)
			{
				Mdis[x]=max(Mdis[x],maxdis);
				maxdis=tmp;id=y;
			}
			else Mdis[x]=max(Mdis[x],tmp);
		}
	}
	MSdis[x]=maxdis;MS[x]=id;
	return maxdis;
}
void DFS2(ll x,ll f,ll d)
{
	ll i,y;
	Fdis[x]=max(Fdis[f]+d,Fdis[x]);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)
		{
			if(y!=MS[x])Fdis[y]=max(Fdis[y],MSdis[x]+LE[i]);
			else Fdis[y]=max(Fdis[y],Mdis[x]+LE[i]);
		}
	}
	for(i=LA[x];i;i=NE[i])if(EN[i]!=f)DFS2(EN[i],x,LE[i]);
	V[x]=max(Fdis[x],MSdis[x]);V[x]=(a+V[x])*b%c;
}
void DFS3(ll x,ll f)
{
	ll i,y;
	dis[x][0]=V[f];
	for(i=1;i<=S;i++)dis[x][i]=max(dis[x][i-1],dis[F[x][i-1]][i-1]);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)DFS3(y,x);
	}
}
ll LCA(ll x,ll y)
{
	ll i,t;
	if(dep[x]<dep[y])x^=y^=x^=y;
	t=dep[x]-dep[y];
	for(i=0;i<=S;i++)
	if(t&(1<<i))x=F[x][i];
	if(x==y)return x;
	for(i=S;i>=0;i--)
	if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
	return F[x][0];
}
ll Find1(ll x,ll y,ll p)
{
	if(V[x]>=p)return x;
	for(ll i=S;i>=0;i--)
	{
		if(dis[x][i]<p)x=F[x][i];
		if(dep[x]<dep[y])return -1;
	}
	if(dep[F[x][0]]<dep[y])return -1;
	if(V[F[x][0]]>=p)return F[x][0];
	return -1;
}
ll Find2(ll x,ll y,ll t,ll p)
{
	if(x==y)return V[x]>=p?x:-1;
	while(t>=0&&dep[F[x][t]]<=dep[y])t--;
	if(t<0)
	{
		ll k=F[x][0];
		if(V[k]>=p)return k;
		if(V[x]>=p)return x;
		return -1;
	}
	if(dis[F[x][t]][t]>=p)
	{
		ll k=Find2(F[x][t],y,t,p);
		if(k!=-1)return k;
	}
	if(dis[x][t]>=p)return Find2(x,F[x][t],t,p);
	if(V[x]>=p)return x;
	return -1;
}
int main_main()
{
	ll i,j,k,x,y,z,ans;
	scanf("%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c);
	for(i=1;i<n;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	DFS1(1,0);DFS2(1,0,0);DFS3(1,0);
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		k=LCA(x,y);cnt=0;
		if(k==y)ans=Find1(x,k,z);
		else if(k==x)ans=Find2(y,k,S,z);
		else
		{
			ans=Find1(x,k,z);
			if(ans==-1)ans=Find2(y,k,S,z);
		}
		printf("%lld\n",ans);
	}
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}