【NOIP2018模拟賽2018.8.28】plutotree

題目

題解

–部份分就是最短路嘛就不講了

正解樹上dp，233333

首先要知道我們dp的目的是什麼：

對于一條u到v的路徑，一共就隻有四種情況

1. u和v直接跑lca

2. u跑到最近的葉子，跳到根，再跑到v

3. v跑到最近的葉子，跳到根，再跑到u

4. u和v都跑到最近的葉子，在根相遇

現在我們就發現了，要得到答案，首先要快速的求到每個節點到最近葉子的路徑長度和最大權值

我們就可以dp

設down[i]，是直接向下跑到葉子的情況

設dp[i]，是可以跑回父親節點再到葉子的情況

轉移很簡單，看代碼就好了

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=+;

int n,m;
vector<int>t[MAXN];
int fa[MAXN][];
int w[MAXN];
int maxx[MAXN][];
int deep[MAXN],d[MAXN];
struct hehe{
    int x;
    int y;
}dp[MAXN],down[MAXN];

void hb(hehe &a,hehe b){
    if(a.x>b.x)
        a=b;
    else if(a.x==b.x)
        a.y=max(a.y,b.y);
}


void build(){
    vector<int>q;
    q.push_back();
    deep[]=;
    d[]=w[];
    for(int h=;h<q.size();h++){
        int x=q[h];
        for(int i=;i<t[x].size();i++){
            int v=t[x][i];
            q.push_back(v);
            deep[v]=deep[x]+;
            d[v]=d[x]+w[v];
        }
    }
    for(int j=;j<=;j++)
        for(int i=;i<=n;i++){
            fa[i][j]=fa[fa[i][j-]][j-];
            maxx[i][j]=max(maxx[i][j-],maxx[fa[i][j-]][j-]);
        }
    for(int i=q.size()-;i>=;i--){
        int x=q[i];
        hehe a;
        a.x=down[x].x+w[fa[x][]];
        a.y=max(down[x].y,w[fa[x][]]);
        hb(down[fa[x][]],a);
    }
}

void solve(){
    vector<int>q;
    q.push_back();
    hb(dp[],down[]);
    for(int h=;h<q.size();h++){
        int x=q[h];
        for(int i=;i<t[x].size();i++){
            int v=t[x][i];
            q.push_back(v);
            dp[v]=down[v];
            hehe a;
            a.x=dp[x].x+w[v];
            a.y=max(dp[x].y,w[v]);
            hb(dp[v],a);
        }
    }
}

hehe lca(int x,int y){
    int u=x,v=y;
    int X,Y=max(maxx[x][],maxx[y][]);
    hehe ans;
    if(deep[x]<deep[y]){
        swap(x,y);
        swap(u,v);
    }
    for(int i=;i>=;i--)
        if(deep[fa[x][i]]>=deep[y]){
            Y=max(Y,maxx[x][i]);
            x=fa[x][i];
        }
    Y=max(Y,maxx[x][]);
    if(x==y){
        X=d[u]-d[v]+w[v];
        ans.x=X;
        ans.y=Y;
        return ans;
    }
    for(int i=;i>=;i--)
        if(fa[x][i]!=fa[y][i]){
            Y=max(Y,maxx[x][i]);
            x=fa[x][i];
            Y=max(Y,maxx[y][i]);
            y=fa[y][i];
        }
    Y=max(Y,maxx[x][]);
    Y=max(Y,maxx[y][]);
    Y=max(Y,maxx[fa[x][]][]);
    X=d[u]+d[v]-d[fa[x][]]*+w[fa[x][]];
    ans.x=X;
    ans.y=Y;
    return ans;
}

int main(){
//  freopen("plutotree.in","r",stdin);
//  freopen("plutotree.out","w",stdout);
    cin>>n>>m;
    for(int i=;i<n;i++){
        int x;
        scanf("%d",&x);
        t[x].push_back(i+);
        fa[i+][]=x;
    }
    for(int i=;i<=n;i++){
        scanf("%d",&w[i]);
        maxx[i][]=w[i];
    }
    for(int i=;i<=n;i++){
        dp[i].x=down[i].x=<<;
        dp[i].y=down[i].y=;
    }
    for(int i=;i<=n;i++){
        if(!t[i].size()){
            down[i].x=down[i].y=w[i];
            hehe a;
            a.x=w[]+w[i];
            a.y=max(w[],w[i]);
            hb(dp[],a);
        }
    }
    build();
    solve();
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        hehe ans=lca(u,v),now;
        now.x=dp[u].x+d[v];
        now.y=max(dp[u].y,maxx[v][]);
        hb(ans,now);
        now.x=dp[v].x+d[u];
        now.y=max(dp[v].y,maxx[u][]);
        hb(ans,now);
        now.x=dp[u].x+dp[v].x+w[];
        now.y=max(max(dp[u].y,dp[v].y),w[]);
        hb(ans,now);
        printf("%d %d\n",ans.x,ans.y);
    }
    return ;
}