题目描述
给定一棵有\(n\)个节点的树，根节点为\(1\)，节点\(i\)有权值\(w[i]\)。这棵树非常奇怪，它的每个叶子结点都有一条连向根节点的权值为\(0\)的边。给定\(q\)次询问，每次给定\(u,v\)，请计算出一条\(u\)到\(v\)的路径（每条边最多经过\(1\)次），最小化该路径上的点权之和，并在其基础上最大化该路径上的最大点权。
输入的第\(1\)行\(2\)个整数表示\(n\)和\(q\)；第\(2\)行有\(n-1\)个正整数，第\(i\)个正整数表示节点\(i+1\)的父节点是\(i\)；第\(3\)行\(n\)个整数，第\(i\)个整数表示\(w[i]\)；接下来\(q\)行，每行\(2\)个整数\(u,v\)，表示一次查询。
输出\(1\)行\(2\)个整数，表示点权和与最大点权。
- \(1\le n,q\le 10^5\)
- \(0\le w[i]\le 10^9\)。
Sample #1
Input:
5 1
1 2 3 4
413 127 263 869 960
Output:
1373 960
解题思路
下面所说的“树上”均之未添加特殊边的树上，“距离”均指路径的点权和。
我们分类讨论，答案显然可以分为下面\(4\)种：
- \(u\)和\(v\)经树上的最短路径，在\(lca(u,v)\)处相遇。
- \(u\)从最近的叶子结点到根节点，\(v\)通过树上路径到根节点，在根节点相遇。
- \(u\)通过树上路径到根节点，\(v\)从最近的叶子结点到根节点，在根节点相遇。
- \(u,v\)都通过最近的叶子节点到根节点，在根节点相遇。
虽然上面的部分情况可能走重复边，但这样它就一定不是最优答案了，所以不影响。
所以我们要处理的是：
- \(u\)到\(v\)在树上的距离和路径上最大点权。
- \(u\)到最近叶子节点的距离和路径上最大点权。
前者可以直接用倍增求LCA来实现。而后者可以通过\(2\)次dfs来实现：
- 用结构体变量
leaf[u]来表示\(u\)到最近叶子节点的信息（距离\(x\)和最大点权\(y\)）。 - 对于叶子结点，初始令
leaf[u]={w[u],w[u]}；
对于其他节点，初始令leaf[u]={+inf,w[u]}。 - 第\(1\)次dfs，自下而上更新\(leaf\)，即\(leaf[u]\)仅考虑了\(u\)子树中的叶子结点。
搜索完子节点\(i\)后，leaf[u]=upd(leaf[u],{leaf[i].x+w[u],leaf[i].y})。 - 第\(2\)次dfs，自上而下再更新一次\(leaf\)，完成\(leaf\)的计算。
搜索子节点\(i\)之前，leaf[i]=upd(leaf[i],{leaf[u].x+w[i],leaf[u].y})。 - 其中
upd()是用于更新答案的，根据定义执行即可：\(x\)不同取最小，\(x\)相同\(y\)取最大。
这样就完成了，对于每次查询更新\(4\)次答案即可，答案和LCA函数也用相同的结构体类型来存储即可，具体见代码。
时间复杂度\(O((n+q)\log n)\)。
Code
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 100010
#define Q 100010
using namespace std;
struct res{int x,y;}leaf[N];
void update(res& a,res b){
if(b.x<a.x) a=b;
else if(b.y==a.y) a.y=max(a.y,b.y);
}
int n,q,w[N],dep[N],fa[N][20],maxx[N][20],d[N];
vector<int> G[N];
void dfs1(int u){//计算d,dep，并自下而上更新leaf
dep[u]=dep[fa[u][0]]+1;
if(G[u].empty()) leaf[u]={w[u],w[u]};
else leaf[u]={LLONG_MAX,w[u]};
for(int i:G[u]){
d[i]+=d[u];
dfs1(i);
update(leaf[u],{leaf[i].x+w[u],leaf[i].y});
}
}
void dfs2(int u){//自上而下再更新一次leaf，完成leaf的计算
for(int i:G[u]){
update(leaf[i],{leaf[u].x+w[i],leaf[u].y});
dfs2(i);
}
}
res LCA(int u,int v){//返回{距离,最大点权}
if(dep[u]<dep[v]) swap(u,v);
int tmax=max(w[u],w[v]),tdis=d[u]+d[v];
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])
tmax=max(tmax,maxx[u][i]),
u=fa[u][i];
if(u==v) return {tdis-d[u]-d[fa[u][0]],tmax};
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
tmax=max(tmax,max(maxx[u][i],maxx[v][i])),
u=fa[u][i],v=fa[v][i];
int lca=fa[u][0];
tmax=max(tmax,max(maxx[u][1],maxx[v][1]));
return {tdis-d[lca]-d[fa[lca][0]],tmax};
}
signed main(){
cin>>n>>q;
for(int i=2;i<=n;i++){
cin>>fa[i][0];
G[fa[i][0]].emplace_back(i);
}
for(int i=1;i<=n;i++){
cin>>w[i];
d[i]=maxx[i][0]=w[i];
}
dfs1(1),dfs2(1);
for(int j=1;j<=19;j++){
for(int i=1;i<=n;i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
maxx[i][j]=max(maxx[i][j-1],maxx[fa[i][j-1]][j-1]);
}
}
while(q--){
int u,v;
cin>>u>>v;
res ans=LCA(u,v);//1. u,v在LCA相遇
update(ans,{leaf[u].x+d[v],max(leaf[u].y,maxx[v][19])});//2. u去叶子v去根
update(ans,{leaf[v].x+d[u],max(leaf[v].y,maxx[u][19])});//3. v去叶子u去根
update(ans,{leaf[u].x+leaf[v].x+w[1],max(max(leaf[u].y,leaf[v].y),w[1])});//4. u,v都去叶子
cout<<ans.x<<" "<<ans.y<<"\n";
}
return 0;
}
变量含义说明：
- \(d[u]\)：\(u\)到根节点的距离。
- \(maxx[u][i]\)：\(u\)向上\(2^i\)个节点（包括\(u\)）的最大权值。