社区讨论
求卡常qwq
CF1827E Bus Routes参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo5pm3ct
- 此快照首次捕获于
- 2023/10/25 20:06 2 年前
- 此快照最后确认于
- 2023/10/25 20:28 2 年前
代码一直卡不过去,求卡
CPP#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
const int K=20;
vector<int>E[N+5];
int n,m,low[N+5],dep[N+5],st[N+5][K+5];
inline int read(){
int x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(isdigit(c)){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
inline void clearAll(){
for(int i=1;i<=n;i++){
low[i]=0;
E[i].clear();
memset(st[i],0,sizeof st[i]);
}
}
void dfs(int u,int fa){
low[u]=u;
dep[u]=dep[fa]+1;
st[u][0]=fa;
for(register int i=0;i<E[u].size();++i){
int v=E[u][i];
if(v==fa){
continue;
}
dfs(v,u);
}
}
inline void build(){
for(register int j=1;j<=K;++j){
for(register int i=1;i<=n;++i){
st[i][j]=st[st[i][j-1]][j-1];
}
}
}
inline int getlca(int u,int v){
if(dep[u]>dep[v]){
swap(u,v);
}
for(register int i=K;~i;--i){
if(dep[st[v][i]]>=dep[u]){
v=st[v][i];
}
}
if(u==v){
return u;
}
for(register int i=K;~i;--i){
if(st[u][i]!=st[v][i]){
u=st[u][i];
v=st[v][i];
}
}
return st[u][0];
}
inline int getKthfa(int u,int k){
for(register int i=K;~i;--i){
int val=1<<i;
if(k>=val){
k-=val;
u=st[u][i];
}
}
return u;
}
pair<int,int>ans;
bool isAns;
void dfs2(int u,int fa){
for(register int i=0;i<E[u].size();++i){
int v=E[u][i];
if(v==fa){
continue;
}
dfs2(v,u);
if(dep[low[u]]>dep[low[v]]){
low[u]=low[v];
}
}
if(fa&&low[u]==u){
isAns=0;
ans.first=u;
ans.second=fa;
}
}
struct node{
int pos,upfa;
friend bool operator<(node A,node B){
return dep[A.upfa]<dep[B.upfa];
}
}a[N+5];
int q[N+5][2];
inline bool solve(){
isAns=1;
n=read(),m=read();
clearAll();
for(register int i=1;i<n;++i){
int u=read(),v=read();
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1,0);
build();
for(register int i=1;i<=m;++i){
int u=read(),v=read();
q[i][0]=u,q[i][1]=v;
int lca=getlca(u,v);
if(dep[lca]<dep[low[u]]){
low[u]=lca;
}
if(dep[lca]<dep[low[v]]){
low[v]=lca;
}
}
dfs2(1,0);
if(!isAns){
return 0;
}
for(register int i=1;i<=n;++i){
a[i].pos=i;
a[i].upfa=low[i];
}
sort(a+1,a+n+1);
for(register int i=1;i<n;++i){
int u=a[i].upfa,v=a[i+1].upfa;
if(getKthfa(v,dep[v]-dep[u])!=u){
ans.first=a[i].pos,ans.second=a[i+1].pos;
return 0;
}
}
int rt=a[n].upfa;
dfs(rt,0);
build();
for(register int i=1;i<=m;++i){
int u=q[i][0],v=q[i][1];
int lca=getlca(u,v);
if(dep[lca]<dep[low[u]]){
low[u]=lca;
}
if(dep[lca]<dep[low[v]]){
low[v]=lca;
}
}
dfs2(rt,0);
for(register int i=1;i<=n;++i){
if(low[i]!=rt){
ans.first=a[n].pos;
ans.second=i;
return 0;
}
}
return 1;
}
int main(){
int T=read();
while(T--){
if(solve()){
putchar('Y');
putchar('E');
putchar('S');
putchar('\n');
}else{
putchar('N');
putchar('O');
putchar('\n');
write(ans.first);
putchar(' ');
write(ans.second);
putchar('\n');
}
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...