全WA。。。。什么鬼啊
查看原帖
全WA。。。。什么鬼啊
44988
IU李知恩的粉丝楼主2020/10/21 14:30
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ri register int
#define rll register long long
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define IOS std::ios::sync_with_stdio(false)
#define L(a) a<<1
#define R(a) a<<1|1
#define P pair<int,int>
#define pii pair<ll,ll>
#define re(x) read(x)
#define lowbit(x) ((x)&-(x))
#define all(x) (x).begin(),(x).end()
#define Pi 3.1415926
#define rg register
#define gcd(x,y) __gcd(x,y)
#define unq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define mem(x,k) memset(x,k,sizeof x)

// #define LOCAL orz
// #define Debug

template<typename T>
inline void read(T& t){
    t = 0;int f = 1;char ch = getchar();while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }while (isdigit(ch)) { t = t * 10 + ch - '0'; ch = getchar(); }t *= f;
}
#ifdef Debug
void DEBUG(string s,int x){cout<<s<<"->:"<<x<<endl;}
void DEBUG(char x){cout<<x<<endl;}
void DEBUG(string x){cout<<x<<endl;}
#endif
void TEST(){cout<<"OK!!!"<<endl;}
const int dx[4]={1,-1,1,-1};
const int dy[4]={-1,1,1,-1};
// const int ddx[4]={0,1,0,-1};
// const int ddy[4]={1,0,-1,0k;
// const int dx[8]={0,-1,0,1,-1,1,1,-1};
// const int dy[8]={-1,0,1,0,1,-1,1,-1};
const int inf=0x3f3f3f3f;
const int mod=998244353;
//const ll inf=9e18;

const double eps=1e-5;
const int maxn=1e6+10;


int head[maxn];

struct Edge
{
    int to,val,next;
}edge[maxn<<1];
void add_edge(int from,int to,int val){
    static int k=0;
    edge[++k].to=to;
    edge[k].val=val;
    edge[k].next=head[from];
    head[from]=k;
}

int depth[maxn];
int fa[maxn][30];
void dfs(int now,int fath){
	fa[now][0]=fath;
	depth[now]=depth[fath]+1;
	for(int i=1;(1<<i)<=depth[now];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];	
	}
	for(int i=head[now];~i;i=edge[i].next){
		int v=edge[i].to;
		if(v!=fath) dfs(v,now);
	}
}
int lca(int x,int y){
	if(depth[x]>depth[y]) swap(x,y);
	for(int i=20;i>=0;i--){
		if(depth[x]<=depth[y]-(1<<i)) y=fa[y][i];
	}
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}

int dis(int x,int y){
    return depth[x]+depth[y]-2*depth[lca(x,y)];
}

int work(int x,int y,int z){
    int Lca=lca(x,y);
    // cout<<dis(x,Lca)<<endl;
    return dis(x,Lca)+dis(y,Lca)+dis(z,Lca);
}

P p[5];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
    freopen("ans.out","w",stdout);
    clock_t start = clock();
#endif

#ifdef Debug
    // cout<<endl<<"调式!!!!记得关!!!";
    cout<<"Debug Start:"<<endl;
#endif
//-------------------------beg-----------------------------------------------------
    
    mem(head,-1);
    int n,m;
    re(n);re(m);
    fp(i,1,n-1){
        int u,v;
        re(u);re(v);
        add_edge(u,v,1);
        add_edge(u,v,1);
    }
    dfs(1,0);
    fp(i,1,m){
        int a,b,c;
        re(a);re(b);re(c);
        p[1]=make_pair(work(a,b,c),lca(a,b));
        p[2]=make_pair(work(b,c,a),lca(b,c));
        p[3]=make_pair(work(a,c,b),lca(a,c));
        int pos=1;
        if(p[2].first<p[pos].first) pos=2;
        if(p[3].first<p[pos].first) pos=3;
        printf("%d %d\n",p[pos].second,p[pos].first);
        // cout<<ans<<endl;
    }
    
//-------------------------end-----------------------------------------------------

#ifdef LOCAL
    clock_t end = clock();
    cout<<"Runing Time: "<<(double)(end-start)/CLOCKS_PER_SEC*1000<<"ms"<<endl;
#endif
    return 0;
}
2020/10/21 14:30
加载中...