Fork me on GitHub

Codeforces418D

Codeforces418D题解

题意:

  • 给出一颗$n$个点的树,$m$次询问离给定两个点距离较小值的最大值。
  • $n \leq 10^5,m \leq 10^5$

题解:

  • 首先找出直径。
  • 将直径上的点按照离一端距离标号。
  • 然后$f,g$数组维护在直径上各标号所对应树上离两端的最大距离,用$rmq$维护。
  • 每次询问时,先算这两个点到直径两端距离。
  • 然后将这两个点假想拉到直径上,算出中点,拆成两段通过$f,g$数组计算。

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define mid (l+r>>1)
#define N 100009
using namespace std;
int n,Q,first[N],number,root[N],fa[N],dis[N],f[N][20],g[N][20],bit[20],lg[N],X,Y;
struct edge
{
int to,next;
void add(int x,int y)
{
to=y,next=first[x],first[x]=number;
}
}e[N<<1];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
int bfs(int x,int from)
{
int ret=0;
queue<int> q;
while (!q.empty()) q.pop();
dis[x]=0,root[x]=from,fa[x]=from;
q.push(x);
while (!q.empty())
{
int now=q.front();
q.pop();
if (dis[ret]<dis[now]) ret=now;
for (int i=first[now];i;i=e[i].next)
if (e[i].to!=fa[now])
{
dis[e[i].to]=dis[now]+1,root[e[i].to]=from,fa[e[i].to]=now;
q.push(e[i].to);
}
}
return ret;
}
int rmq(int f[][20],int x,int y)
{
if (x>y) return 0;
int k=lg[y-x+1];
return max(f[x][k],f[y-bit[k]+1][k]);
}
void init()
{
//ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
bit[0]=1;
for (int i=1;i<20;i++) bit[i]=bit[i-1]<<1;
lg[0]=-1;
for (int i=1;i<N;i++) lg[i]=lg[i>>1]+1;
n=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
e[++number].add(x,y),e[++number].add(y,x);
}
int x=bfs(1,0);
int y=bfs(x,0);
for (int i=y,j=0;i;j=i,i=fa[i])
{
int Max=0;
root[i]=i;
for (int k=first[i];k;k=e[k].next)
if (e[k].to!=fa[i]&&e[k].to!=j)
Max=max(Max,dis[bfs(e[k].to,i)]+1);
f[dis[i]][0]=Max+dis[i];
g[dis[i]][0]=Max+dis[y]-dis[i];
}
for (int i=1;i<20;i++)
for (int j=1;j+bit[i]-1<=dis[y];j++)
{
f[j][i]=max(f[j][i-1],f[j+bit[i-1]][i-1]);
g[j][i]=max(g[j][i-1],g[j+bit[i-1]][i-1]);
}
X=x,Y=y;
}
void work()
{
Q=read();
while (Q--)
{
int x=read(),y=read();
int l=dis[root[x]],r=dis[root[y]];
if (l<r) swap(l,r),swap(x,y);
int dx=0,dy=0;
if (x!=root[x]) l+=dis[x]+1,dx=dis[x]+1,x=root[x];
if (y!=root[y]) r-=dis[y]+1,dy=dis[y]+1,y=root[y];
int ret=min(dx+dis[Y]-dis[x],dy+dis[Y]-dis[y]);
ret=max(ret,min(dx+dis[x],dy+dis[y]));
ret=max(ret,rmq(f,dis[y]+1,min(mid,dis[x]))-r);
ret=max(ret,rmq(g,max(mid+1,dis[y]),dis[x]-1)-(dis[Y]-l));
printf("%d\n",ret);
}
}
int main()
{
init();
work();
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces418D

文章作者:wzf2000

发布时间:2017年12月23日 - 22:12

最后更新:2017年12月26日 - 03:12

原始链接:https://wzf2000.github.io/2017/12/23/Codeforces418D/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。