uoj126 快餐店

发表于 | 更新于

Link

Solution

如果在树上的话，答案显然就是树的直径÷2\div 2。然后发现这道题的距离可以是实数，似乎不好设计状态DP，于是思考如何向树上转化。 基环树，处理的最常见的思路也就是拆环了(一个LCT好题)。那么把这个图的环枚举边拆掉，是不是直接求直径就行了？ 然后观察一下，发现不管把点放在哪里，环上一定有一条边是不会被经过的。所以只要枚举断点拆环，得到的直径的最小值÷2\div 2就是答案了。 至于直径，一定是来源于环上挂着的子树的直径，或者是一个子树的一条链，经过环走到另一个子树。 第一种可以预处理 至于第二种，感觉做法挺有意思的。 设当前断点为pp，其它所有点uu到pp的距离为d[u]d[u]，每个子树中的最长链为ch[u]ch[u]，那么这个答案就是 把变量分离开，发现就是个max{d[v]+ch[v]+(−d[u]+ch[u])}max\{d[v]+ch[v]+(-d[u]+ch[u])\}只需要维护d[u]+ch[u]d[u]+ch[u]的最大值，和−d[u]+ch[u]-d[u]+ch[u]的最小值即可！ 所以建立两个线段树分别维护着两个量，那么当枚举的断边改变的时候该如何实时修改线段树的信息呢？ 发现，如果硬是要维护到断点的距离的话，那么d[]d[]就会这样变化： 0,d[2],d[3],d[4]..→d[n]+dist(n,1),0,d[3]−d[2],d[4]−d[2]→...0,d[2],d[3],d[4]..\rightarrow d[n]+dist(n,1),0,d[3]-d[2],d[4]-d[2]\rightarrow... 似乎比较麻烦的样子？ 然而本来这个d[]d[]就是个前缀和，需要的只是它两项的差值。只要维护相对大小正确就行了。于是修改断边，只需要修改一个点的值就可以，直接把它的dd设置为它的前驱predpred的d[pred]+dist(pred,this)d[pred]+dist(pred,this)即可。。虽然比较显然，但我还是感觉比较有意思。。

Tips

维护前缀和数组，可以只需要维护值的差正确 基环树先想拆环

Code

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long int64;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::pair;
using std::partial_sum;
using std::swap;
using std::make_pair;
using std::max;

const int MAXN=1e5+11;
struct Info
{
	pair<int64,int> fmx,smx;
	Info(){fmx=smx=make_pair(LLONG_MIN,-1);}
	Info(pair<int64,int> mx):fmx(mx),smx(LLONG_MIN,-1){}
	Info(pair<int64,int> fmx,pair<int64,int> smx):fmx(fmx),smx(smx){}
	friend Info operator +(Info a,Info b)
	{
		if(a.fmx<b.fmx) swap(a,b);
		return Info(a.fmx,max(a.smx,b.fmx));
	}
};
namespace _SegTree_
{
	const int SIZE=MAXN<<2;
	struct Node
	{
		Node *son[2];
		Info mx;
		Node();
		void *operator new(size_t);
		void Up();
	}*Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool,*null=new Node;
	void *Node::operator new(size_t){return Me++;}
	Node::Node(){son[0]=son[1]=null;}
	void Node::Up(){mx=son[0]->mx+son[1]->mx;}
	struct SegTree
	{
		int L,R;
		Node *root;
		SegTree(int L,int R):L(L),R(R),root(null){}
		void Edit(Node *&,int,int,int,pair<int64,int>);
		void Insert(int pos,pair<int64,int> mark){Edit(root,L,R,pos,mark);}
	};
	void SegTree::Edit(Node *&pos,int L,int R,int goal,pair<int64,int> mark)
	{
		if(pos==null)
			pos=new Node;
		if(L==R)
			pos->mx=mark;
		else
		{
			int Mid=(L+R)>>1;
			if(goal<=Mid)
				Edit(pos->son[0],L,Mid,goal,mark);
			else
				Edit(pos->son[1],Mid+1,R,goal,mark);
			pos->Up();
		}
	}
}using _SegTree_::SegTree;
struct Edge
{
	int to,v;Edge* pre,*rev;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre),rev(0){}
}*Edge_Me=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Edge_Pool=Edge_Me,*id[MAXN];
int n;
void Adde(int f,int t,int v)
{
	id[f]=new(Edge_Me++) Edge(t,v,id[f]);
	id[t]=new(Edge_Me++) Edge(f,v,id[t]);
	id[f]->rev=id[t];id[t]->rev=id[f];
}
struct CirclePoint
{
	int id;
	int64 longch;
}circle[MAXN];
int cc,ref[MAXN];
int64 pref[MAXN],len[MAXN];
bool DFS(int pos,int fa)
{
	static int pred[MAXN]={0,-1};
	for(Edge *e=id[pos];e;e=e->pre)
	{
		int u=e->to;
		if(u==fa) continue;
		if(pred[u])
		{
			while(pos!=pred[u])
			{
				circle[++cc].id=pos;
				pos=pred[pos];
			}
			return 1;
		}
		pred[u]=pos;
		if(DFS(u,pos)) return 1;
	}
	return 0;
}
bool ban[MAXN];
int BFS(int pos,int64 *dist)
{
	static int us[MAXN],ut,Q[MAXN],he,ta;
	dist[pos]=0;
	us[Q[he=ta=1]=pos]=++ut;
	int64 mxd=LLONG_MIN;int res=0;
	while(he<=ta)
	{
		int cur=Q[he++];
		for(Edge *e=id[cur];e;e=e->pre)
		{
			int u=e->to;
			if(us[u]==ut || ban[u]) continue;
			dist[u]=dist[cur]+e->v;//dist[pos]..
			Q[++ta]=u;us[u]=ut;
			if(chkmx(mxd,dist[u])) res=u;
		}
	}
	return res;
}
int64 Prep()
{
	DFS(1,0);
	static int64 dist[MAXN];
	for(int i=1;i<=cc;++i)
	{
		int pos=circle[i].id;
		ref[pos]=i;
		ban[pos]=1;
	}
	int64 res=LLONG_MIN;
	for(int i=1;i<=cc;++i) 
	{
		int pos=circle[i].id;
		int p=BFS(pos,dist);
		circle[i].longch=dist[p];
		ban[pos]=0;
		int f=BFS(p,dist);
		ban[pos]=1;
		chkmx(res,dist[f]);
	}
	return res;
}
int main()
{
	get(n);
	for(int i=1;i<=n;++i)
	{
		int a,b,l;get(a),get(b),get(l);
		Adde(a,b,l);
	}
	int64 Temp=Prep();
	#define pred(x,C) (x!=1?x-1:C)
	#define succ(x,C) (x!=C?x+1:1)
	for(Edge *e=Edge_Pool;e!=Edge_Me;++e)
	{
		int t=e->to,f=e->rev->to;
		if(ref[f] && ref[t] && succ(ref[f],cc)==ref[t])
			len[ref[t]]=e->v;
	}
	partial_sum(len+2,len+1+cc,pref+2);
	SegTree seg1(1,cc),seg2(1,cc);
	#define Updata(i) seg1.Insert(i,make_pair(circle[i].longch+pref[i],i)),seg2.Insert(i,make_pair(circle[i].longch-pref[i],i))
	for(int i=1;i<=cc;++i)
		Updata(i);
	int64 Ans=LLONG_MAX;
	for(int i=1;i<=cc;++i)
	{
		Info mx1=seg1.root->mx,mx2=seg2.root->mx;
		chkmn(Ans,mx1.fmx.second==mx2.fmx.second?max(mx1.fmx.first+mx2.smx.first,mx1.smx.first+mx2.fmx.first):mx1.fmx.first+mx2.fmx.first);
		pref[i]=pref[pred(i,cc)]+len[i];
		Updata(i);
	}
	chkmx(Ans,Temp);
	printf("%.1lf\n",(double)Ans/2);
	return 0;
}