警示后人! 如果你52分
查看原帖
警示后人! 如果你52分
1318046
Yuukiyo楼主2024/11/30 13:27

如果你错误点是这样的

不用特判x==y的情况,具体见注释代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
struct node{LL v,w;};
LL n,q,c[N],f[N],g[N],dep[N],fat[N][21],mx[N][21],sum[N];
vector<node>e[N];
void dfs(LL u,LL fa) {
    f[u]=c[u];
    for (node t:e[u]) {
        LL v=t.v,w=t.w;
        if (v==fa) continue;
        dfs(v,u);
        f[u]=max(f[u],f[v]-2*w);
    }
}
void dfs2(LL u,LL fa) {
    for (node t:e[u]) {
        LL v=t.v,w=t.w;
        if (v==fa) continue;
        g[v]=max(f[v],g[u]-2*w);
        dfs2(v,u);
    }
}
void dfs3(LL u,LL fa) {
    dep[u]=dep[fa]+1,fat[u][0]=fa;mx[u][0]=max(g[0],g[fa]);
    for (LL i=1;i<=20;++i) fat[u][i]=fat[fat[u][i-1]][i-1],mx[u][i]=max(mx[u][i-1],mx[fat[u][i-1]][i-1]);
    for (node t:e[u]) {
        if (t.v==fa) continue;
        sum[t.v]=sum[u]+t.w;
        dfs3(t.v,u);
    }
}   
int main() {
    scanf("%lld %lld",&n,&q);
    for (LL i=1;i<=n;++i) scanf("%lld",&c[i]);
    for (LL i=1,u,v,w;i<n;++i) {
        scanf("%lld %lld %lld",&u,&v,&w);
        e[u].push_back({v,w});e[v].push_back({u,w});
    }
    dfs(1,0);g[1]=f[1];dfs2(1,0);dfs3(1,0);
    for (LL i=1,x,y,m,a,b,lc,s;i<=q;++i) {
        scanf("%lld %lld",&x,&y);
        m=max(g[x],g[y]); a=x,b=y;
        //if (x==y) {printf("%lld\n",c[x]*3);continue;}  不用特判
        if (dep[x]<dep[y]) swap(x,y);
        for (LL j=20;~j;--j) {
            if (dep[fat[x][j]]>=dep[y]) m=max(m,mx[x][j]),x=fat[x][j];
        }
        if (x==y) lc=x;
        else {
            for (LL j=20;~j;--j) {
            if (fat[x][j]!=fat[y][j]) m=max(m,max(mx[x][j],mx[y][j])),x=fat[x][j],y=fat[y][j];
            }
            lc=fat[x][0];m=max(m,g[lc]);
        }
        s=sum[a]+sum[b]-2*sum[lc];
        printf("%lld\n",c[a]+c[b]+m-s);
    }
    return 0;
}
2024/11/30 13:27
加载中...