样例过了但是爆零,求Hack
查看原帖
样例过了但是爆零,求Hack
999274
CNS_5t0_0r2楼主2024/7/30 14:09
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9;
struct edge{
    int to,nex;
} e[N << 1];
int ecnt,head[N];
int top[N],dep[N];
int fa[N],w_ch[N],siz[N];
int n,m;
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
void dfs1(int cur,int father){
    fa[cur] = father;
    siz[cur] = 1;
    dep[cur] = dep[father] + 1;
    for(int i = head[cur];i;i = e[i].nex){
        int v = e[i].to;
        if(v != father){
            dfs1(v,cur);
            siz[cur] += siz[v];
            if(siz[v] > siz[w_ch[cur]])
                w_ch[cur] = v;
        }
    }
}
void dfs2(int cur,int link_top){
    top[cur] = link_top;
    if(w_ch[cur]){
        dfs2(w_ch[cur],link_top);
        for(int i = head[cur];i;i = e[i].nex){
            int v = e[i].to;
            if(v != fa[cur] && v != w_ch[cur])
                dfs2(v,v);
        }
    }
}
int LCA(int u,int v){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]])
            swap(u,v);
        u = fa[top[u]];
    }
    return (dep[u] < dep[v]) ? u : v;
}

int path(int u,int v){
	int lca = LCA(u,v);
	return dep[u] + dep[v] - (dep[lca] << 1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
        addedge(v,u);
    }
    dep[1] = 1;
    dfs1(1,0);
    dfs2(1,0);
    while(m--){
        int u[5];
        cin >> u[1] >> u[2] >> u[3];
        int lca1 = LCA(u[1],u[2]);
        int lca2 = LCA(u[1],u[3]);
        int lca3 = LCA(u[2],u[3]);
        if(lca1 == lca2 && lca2 == lca3)
        	cout << lca1 << ' ' << 0ll + path(u[1],lca1) + path(u[2],lca1) + path(u[3],lca1) << '\n';
        else if(lca1 == lca2)
        	cout << lca3 << ' ' << 0ll + path(u[1],lca3) + path(u[2],lca3) + path(u[3],lca3) << '\n';
        else if(lca1 == lca3)
        	cout << lca2 << ' ' << 0ll + path(u[1],lca2) + path(u[2],lca2) + path(u[3],lca2) << '\n';
        else if(lca2 == lca3)
        	cout << lca3 << ' ' << 0ll + path(u[1],lca1) + path(u[2],lca1) + path(u[3],lca1) << '\n';
    }
    return 0;
}
2024/7/30 14:09
加载中...