P1600
首先肯定要用到 LCA，先用DFS预处理每个节点的第 \(2^k\) 代祖先和每个节点的深度，倍增计算LCA即可。
最直接的做法是模拟每个人跑步的过程，但这种方法的最差复杂度是 \(O(nm)\)，肯定会超。
考虑优化模拟过程，将模拟玩家改为枚举观察员，计算有几名玩家会为观察员做贡献。
对于观察员 \(P\)，如果它位于 \((s_i,t_i)\) 的跑步路径上，可以分情况讨论选手能不能为 \(P\) 作贡献。
- \(P\) 位于 \((s_i,LCA(s_i,t_i))\) 上：当 \(dep[s_i]-dep[P]=W[P]\) 时，可以做出贡献。
- \(P\) 位于 \((LCA(s_i,t_i),t_i)\) 上：当 \(d(s_i,t_i)-dep[t_i]-dep[P]=w[P]\) 时，可以做出贡献。
但无论是哪种情况，可以贡献的起点或终点一定在以 \(P\) 为根的子树上，这给我们一边回溯一边统计创造了遍历。
对于树上任意一个起点和终点，将其产生的贡献放入一个桶中，回溯时到桶里面查询贡献。但是注意：以 \(P\) 为根递归整棵子树过程中在桶内产生的差值才是对 \(P\) 真正的贡献。
还有一种特殊情况：如果路径的起点或终点为 \(LCA\)，且可以被观察到，那么会重复计算一次，应该减去。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=6e5+9;
ll n,m,s[N],t[N],w[N],ans[N],dep[N],p[N][29],dist[N],cnts[N];
ll b1[N],b2[N];
vector<int> to[N];
vector<int> end_set[N],lca_set[N];
void dfs_pre(int x,int fa){
dep[x]=dep[fa]+1; p[x][0]=fa;
for(int i=1;i<=28;i++) p[x][i]=p[p[x][i-1]][i-1];
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(y==fa) continue;
dfs_pre(y,x);
}
}
int LCA(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int i=28;i>=0;i--){
if(dep[p[v][i]]>=dep[u]) v=p[v][i];
}
if(u==v) return u;
for(int i=28;i>=0;i--){
if(p[u][i]!=p[v][i]){
u=p[u][i]; v=p[v][i];
}
}
return p[u][0];
}
void dfs(int x,int fa){
int bkt1=b1[w[x]+dep[x]],bkt2=b2[w[x]-dep[x]];
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(y==fa) continue;
dfs(y,x);
}
b1[dep[x]]+=cnts[x];
for(int i=0;i<end_set[x].size();i++){
int y=end_set[x][i];
b2[dist[y]-dep[t[y]]]++;
}
ans[x]+=(b1[w[x]+dep[x]]+b2[w[x]-dep[x]]-bkt1-bkt2);
for(int i=0;i<lca_set[x].size();i++){
int y=lca_set[x][i];
b1[dep[s[y]]]--;
b2[dist[y]-dep[t[y]]]--;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int u,v; cin>>u>>v;
to[u].push_back(v); to[v].push_back(u);
}
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=m;i++) cin>>s[i]>>t[i];
dfs_pre(1,0);
for(int i=1;i<=m;i++){
int lca_st=LCA(s[i],t[i]);
dist[i]=dep[s[i]]+dep[t[i]]-2*dep[lca_st];
cnts[s[i]]++;
end_set[t[i]].push_back(i);
lca_set[lca_st].push_back(i);
if(dep[lca_st]+w[lca_st]==dep[s[i]]) ans[lca_st]--;
}
dfs(1,0);
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
P1967
题目大意：给出一张 \(n\) 点 \(m\) 边的带权无向图，求任意两点间路径最小边权最大值，无法到达输出 \(-1\)。
首先考虑无解的情况，可以使用并查集判定。每输入一条边，就把这条边的两个端点并入同一个集合。问询时如果起点和终点不在同一个集合内，就输出 \(-1\)。
对于有解的问询，解法较多。
-
最大生成树+倍增：对每一个连通块构造最大生成树，将原问题转化为 “树上 \(x\) 到 \(y\) 路径之间的最小权值”，可以使用倍增求解。
-
Kruskal重构树：Kruskal重构树 详解。对于本题，在 Kruskal 的过程中，若当前 \(u,v\) 两点不在同一个并查集内，则新建一个节点 \(node\)，其点权为 \((u,v)\) 的边权，接着 \(root(u)=node,root(v)=node\)。
重构完成后，制定每个集合的根作为所在森林的根，则 \((u,v)\) 路径上的最小边权最大值就是 \(lca(u,v)\) 的点权。
-
最大生成树+set：要求x到y所有的路径中最小边长的最大值，可以贪心地加边，依照边从大往小的方式往里添加，然后合并并查集。 每次当查询分布在两个待合并的并查集的时候，当前的边长就是这次查询的答案。
我们对每个并查集维护一个集合，集合中保存的内容就是一个点在这个并查集中，而另一个点不在这个并查集中的询问编号。
当待合并的两个并查集所具有的集合里面拥有相同的询问编号时候，回答这个询问编号，然后把小的集合向大的集合合并，并将回答完的询问编号从集合中移除。
此处给出方法 \(2\) 的代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
int u,v,w;
}E[100009];
bool vst[100009];
int n,m,q,tot,s[100009],t[100009],fa[100009],val[100009],dep[100009];
int p[100009][19];
vector<int> to[100009];
int root(int x){
return fa[x]==x?x:fa[x]=root(fa[x]);
}
bool cmp(const edge&a,const edge&b){
return a.w>b.w;
}
void dfs_fa(int x,int f){
p[x][0]=f; vst[x]=1; dep[x]=dep[f]+1;
for(int i=1;i<=18;i++) p[x][i]=p[p[x][i-1]][i-1];
for(int i=0;i<to[x].size();i++){
if(to[x][i]==f) continue;
dfs_fa(to[x][i],x);
}
return ;
}
int lca(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int i=18;i>=0;i--){
if(dep[p[v][i]]>=dep[u]) v=p[v][i];
}
if(u==v) return u;
for(int i=18;i>=0;i--){
if(p[u][i]!=p[v][i]){
u=p[u][i]; v=p[v][i];
}
}
return p[u][0];
}
void kruskal(){
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int fu=root(E[i].u),fv=root(E[i].v);
if(fu==fv) continue;
val[++tot]=E[i].w;
fa[tot]=fa[fu]=fa[fv]=tot;
to[tot].push_back(fu); to[fu].push_back(tot);
to[tot].push_back(fv); to[fv].push_back(tot);
}
for(int i=1;i<=tot;i++){
if(vst[i]) continue;
int fi=root(i);
dfs_fa(fi,0);
}
}
int main(){
cin>>n>>m; tot=n;
for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
cin>>q;
for(int i=1;i<=q;i++) cin>>s[i]>>t[i];
sort(E+1,E+1+m,cmp);
kruskal();
for(int i=1;i<=q;i++){
if(root(s[i])!=root(t[i])) cout<<-1<<endl;
else cout<<val[lca(s[i],t[i])]<<endl;
}
return 0;
}
P1084
warning：如果你WA 60pts，可以检查倍增部分，应该先增加用时再往上跳
题目要我们最小化答案，因为答案符合单调性（如果能在 \(x\) 小时内控制，大于 \(x\) 小时一定也能控制），那么我们可以使用二分枚举答案+判定。
容易发现，军队越靠近根节点，可以控制的子节点就更多。那么根据贪心的思想，所有军队都尽量往根节点靠拢。
往上跳的过程一般使用倍增优化，那么我们可以先 DFS 一遍，将倍增用的值处理好（例如第 \(2^k\) 代祖先，跳到它需要的时间等）。
遍历每一个军队，如果当前军队可以到达根节点，那么记录它的编号的它到达根节点后可以走的路程，对于每一个子树 \(x\)，记录可以到达根节点且剩余路程最短的点。反之，记录它能被“提”到的最高节点
如果一个节点建立了检查点或者它的所有子树都设立了检查点，则说明以这个节点为根的子树已经被“封死”。记录根节点的所有子树中，未被“封死”的子树。
将我们记录好的能到根节点的军队按剩余路程从大到小排序，将未被封死的子树按到根节点的距离从远到进排序。依次处理未被封死的子树要由哪支军队管辖。优先安排在同一颗子树中的军队，如果没有，再查看当前没有被使用的军队里剩余路程最大的是否可以到达这颗子树。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50009;
bool vst[N],need[N];
ll n,m,LOG2N,id[N],fa[N][19],dis[N][19],dep[N],rst_need[N];
vector<ll> to[N],w[N];
struct node{ll id,rst;}abled_army[N];
ll rst_army[N];
bool cmp(const node&a,const node&b){
return a.rst<b.rst;
}
void init(){
memset(vst,0,sizeof(vst));
memset(need,0,sizeof(need));
memset(rst_need,0,sizeof(rst_need));
memset(rst_army,0,sizeof(rst_army));
memset(abled_army,0,sizeof(abled_army));
}
void dfs_pre(int x,int f){
for(int i=1;i<=LOG2N;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
dis[x][i]=dis[x][i-1]+dis[fa[x][i-1]][i-1];
}
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(y==f) continue;
fa[y][0]=x; dis[y][0]=w[x][i];
dfs_pre(y,x);
}
}
bool dfs(int x,int fa){
if(vst[x]) return 1;
if(to[x].size()==1) return 0;
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(y==fa) continue;
if(!dfs(y,x)) return 0;
}
return 1;
}
bool ok(int mid){
int cnta=0,cnta2=0,cntb=0;
init();
for(int i=1;i<=m;i++){
ll x=id[i],use=0;
for(int j=LOG2N;j>=0;j--){
if(fa[x][j]>1&&use+dis[x][j]<=mid){
use+=dis[x][j]; x=fa[x][j];
}
}
if(fa[x][0]==1&&use+dis[x][0]<=mid){
abled_army[++cnta].rst=mid-(use+dis[x][0]);
abled_army[cnta].id=x;
}
else vst[x]=1;
}
for(int i=0;i<to[1].size();i++){
if(!dfs(to[1][i],1)) need[to[1][i]]=1;
}
sort(abled_army+1,abled_army+cnta+1,cmp);
for(int i=1;i<=cnta;i++){
int id_now=abled_army[i].id,rst_now=abled_army[i].rst;
if(need[id_now]&&rst_now<dis[id_now][0]) need[id_now]=0;
else rst_army[++cnta2]=rst_now;
}
for(int i=0;i<to[1].size();i++){
if(need[to[1][i]]) rst_need[++cntb]=dis[to[1][i]][0];
}
if(cnta2<cntb) return 0;
sort(rst_army+1,rst_army+1+cnta2);
sort(rst_need+1,rst_need+1+cntb);
int i=1,j=1;
while(i<=cnta2&&j<=cntb){
if(rst_army[i]>=rst_need[j]) j++;
i++;
}
if(j>cntb) return 1;
return 0;
}
int main(){
cin>>n;
LOG2N=log2(n)+1;
for(int i=1;i<n;i++){
int x,y,z; cin>>x>>y>>z;
to[x].push_back(y); to[y].push_back(x);
w[x].push_back(z); w[y].push_back(z);
}
cin>>m;
for(int i=1;i<=m;i++) cin>>id[i];
dfs_pre(1,0);
int l=1,r=1e9,ans=-1;
while(l<=r){
int mid=l+(r-l)/2;
if(ok(mid)){ans=mid;r=mid-1;}
else l=mid+1;
}
cout<<ans<<endl;
return 0;
}
P1099
题目大意：给定一棵带边权无根树，在其直径上选择一段长度不超过 \(s\) 的路径，使其偏心距最小。
直径的性质
1.对于直径上任意一点 \(s\)，到它本身距离最远的点一定是直径的两个端点 \(A_1,A_2\) 之一。
证明：反证法，假设在直径外存在一点 \(t\)，使得 \(d(s,t)>d(s,A_1)\) 且 \(d(s,t)>d(s,A_2)\)，那么 \(d(t,A_1)>d(A_1,A_2)\) 且 \(d(t,A_2)>d(A_1,A_2)\)。这违反了直径的定义。
2.对于一棵正边权的树，如果存在多条直径，一定交于一点。
证明：如果两直径 \((S_1,T_1),(S_2,T_2)\) 没有交于一点， 则对于任意的 \((a,b)\) ，除了 \(a,b\) 两点外，其它点均不在直径上（不说人话：\(∃a \in (S_1,T_1),b \in (S_2,T_2)\)，且 \(∀p \in (a,b)-\{a,b\},p \notin (S_1,T_1),p \notin (S_2,T_2)\)）。设 \(d_1=\max\{d(S_1,a),d(a,T_1)\}\),\(d_2=\max\{d(S_2,b),d(b,T_2)\}\)，则 \(d_1,d_2 \geq \frac{d(S_1,T_1)}{2}\)，则\(d_1+d_2+(a,b)\) 可以拼成一条比直径还长的路径，假设不成立。
3.对于一棵所有边权均为正的树，如果其存在多条直径，则各直径的中点（不一定恰好是某个节点，可能在某条边的内部）是唯一的。
4.若两条直径有重叠的部分，则于重叠部分同一端点引出的两条直径的非重叠的部分的长度相等。
5.若路径存在不位于直径上的部分，这条路径对应的偏心距一定不会比全部位于直径上的路径的偏心距的最小值更小。
多条直径的处理
如果一棵树有多条直径，任选一条即可。由于两条直径不可能相交，那么把相交部分看作一点，剩下部分关于这条直径对称。而如果选择的路径包含了分叉点，其偏心距就是恒定的，所以可以任选一条直径求解。
对偏心距造成影响的因素
设路径的两端点为 \(P_1,P_2\)，直径的两端点为 \(A_1,A_2\)，显然对答案造成影响的有 \(P_1,A_1\) 和 \(P_2,A_2\)。
但这不以为长度越长答案一定越优，因为路径上的其它点对答案也有贡献。路径上其它点 \(Q\) 对答案的贡献为 “不经过路径上其它任何点所能到达的最远距离”。这种贡献可以预处理。
解法
- 枚举：求出树的任意一条直径，然后在直径上枚举端点，接下来 DFS 遍历整棵树，按定义求出其它点到路径的距离，从而得到偏心距。时间复杂度 \(O(n^3)\)。
- 双指针枚举优化：在固定路径一端 \(s\) 的情况下，随着路径的增长，偏心距不会变大。于是可以考虑枚举一个端点，用双指针找到离 \(s\) 最远，且不超过路径上限的点，从而降低候选数量
- 二分：考虑二分偏心距，将最优化问题变成存在性问题。
- 双指针+前缀和：将解法2优化，发现其低效的原因主要在于每次求出最最优区间后都要 dfs一遍，只要在双指针过程中用前缀和维护即可。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+9;
int n,m,k1,k2,d,id,ans=2e9,fa[N],dis[N];
bool vst[N];
vector<int> to[N];
vector<int> w[N];
void dfs(int x,int f){
fa[x]=f;
if(dis[x]>dis[k1]) k1=x;
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(y==f||vst[y]) continue;
dis[y]=dis[x]+w[x][i];
dfs(y,x);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int x,y,z;
cin>>x>>y>>z;
to[x].push_back(y);
to[y].push_back(x);
w[x].push_back(z);
w[y].push_back(z);
}
dis[1]=0; dfs(1,0);
dis[k1]=0; dfs(k1,0);
k2=k1;
for(int i=k2,j=k2;i;i=fa[i]){
while(dis[j]-dis[i]>m) j=fa[j];
d=max(dis[k2]-dis[j],dis[i]);
ans=min(ans,d);
}
for(int i=k2;i;i=fa[i]) vst[i]=1;
for(int i=k2;i;i=fa[i]){
k1=i,dis[k1]=0;
dfs(i,fa[i]);
}
for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
cout<<ans;
return 0;
}