题解
2023-08-19 16:23:08
发布于:广东
29阅读
0回复
0点赞
#include<bits/stdc++.h>
#define maxn 2005
using namespace std;
struct n
{
int f[maxn],x[maxn],r[maxn];
int g(int a) {return f[a]==a?a:f[a]=g(f[a]);}
int i,l,c;
} p[maxn];
int e[maxn<<1],t[maxn<<1],s[maxn],j=1;
int m[maxn],k[maxn],o;
int q;
auto h = [&](int a, int b)
{
e[++j]=s[a];
s[a]=j,t[j]=b;
};
int u(int a,int b)
{
int c=1e9,d;
if(b)
{
if(!p[a].l||b/2==p[a].l)
{
if(!p[a].x[b/2]&&(!p[a].i||(p[a].g(b/2)!=p[a].g(p[a].i))||p[a].c==1)) c=min(c,a),k[a]=0;
}
}
for(int i=s[a];i;i=e[i])
{
int y=t[i]; if(b/2==i/2) continue;
if(!b&&(!p[a].i||p[a].i==i/2))
{
if(!p[a].l||(p[a].g(i/2)!=p[a].g(p[a].l))||p[a].c==1)
{
if(p[a].r[i/2]) continue;
d=u(y,i);
if(d<c) c=d,k[a]=y;
}
}
else
{
if(b/2==p[a].l||i/2==p[a].i||p[a].g(b/2)==p[a].g(i/2)||p[a].x[b/2]||p[a].r[i/2]) continue;
if(!p[a].l||!p[a].i)
{
d=u(y,i);
if(d<c) c=d,k[a]=y;
}
else
{
int ax=p[a].g(b/2),ay=p[a].g(i/2);
int bx=p[a].g(p[a].i),by=p[a].g(p[a].l);
if(ax>ay) swap(ax,ay); if(bx>by) swap(bx,by);
if((bx!=ax||by!=ay)||p[a].c==2)
{
d=u(y,i);
if(d<c) c=d,k[a]=y;
}
}
}
}
return c;
}
void v(int a,int b)
{
if(!k[a])
{
p[a].l=b/2;
return;
}
for(int i=s[a];i;i=e[i])
{
int y=t[i]; if(y!=k[a]) continue;
if(!b) p[a].i=i/2;
else
{
p[a].f[p[a].g(b/2)]=p[a].g(i/2);
p[a].r[i/2]=1,p[a].x[b/2]=i/2;
p[a].c--;
}
v(y,i);
}
};
int main()
{
auto w = [&]()
{
for(int i=1;i<=o;i++)
{
s[i]=0;
memset(p[i].f,0,sizeof(p[i].f));
memset(p[i].r,0,sizeof(p[i].r));
memset(p[i].x,0,sizeof(p[i].x));
p[i].c=p[i].i=p[i].l=0;
}
j=1;
};
cin>>q;
while(q--)
{
cin>>o;
w();
for(int i=1;i<=o;i++) cin>>m[i];
for(int i=1,a,b;i<o;i++) cin>>a>>b,h(a,b),h(b,a);
for(int a=1;a<=o;a++)
for(int i=s[a];i;i=e[i])
p[a].f[i/2]=i/2,p[a].c++;
for(int z=1;z<=o;z++)
{
cout<<u(m[z],0)<<" ";
v(m[z],0);
}
cout<<"\n";
}
return 0;
}
第一道黑题,激动到内牛满面
这里空空如也
有帮助,赞一个