答案与解析
正确答案:<p style="text-align: left;">#include<cstdio></p><p style="text-align: left;">#include<vector></p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)</p><p style="text-align: left;">#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)</p><p style="text-align: left;">#define writc(a,b) fwrit(a),putchar(b)</p><p style="text-align: left;">#define mp(a,b) make_pair(a,b)</p><p style="text-align: left;">#define ft first</p><p style="text-align: left;">#define sd second</p><p style="text-align: left;">#define LL long long</p><p style="text-align: left;">#define ull unsigned long long</p><p style="text-align: left;">#define pii pair<int,int></p><p style="text-align: left;">// #define FILEOI</p><p> </p><p style="text-align: left;">#define cg (c=getchar())</p><p style="text-align: left;">template<class T>inline void qread(T& x){</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c;bool f=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(cg<'0'||'9'<c)if(c=='-')f=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(f)x=-x;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int qread(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0;char c;bool f=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(cg<'0'||'9'<c)if(c=='-')f=-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));</p><p style="text-align: left;"><span style="white-space:pre"> </span>return f?-x:x;</p><p style="text-align: left;">}</p><p style="text-align: left;">#undef cg</p><p style="text-align: left;">template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}</p><p style="text-align: left;">template<class T>inline T Max(const T x,const T y){return x>y?x:y;}</p><p style="text-align: left;">template<class T>inline T Min(const T x,const T y){return x<y?x:y;}</p><p style="text-align: left;">template<class T>inline T fab(const T x){return x>0?x:-x;}</p><p style="text-align: left;">inline void getInv(int inv[],const int lim,const int MOD){</p><p style="text-align: left;"><span style="white-space:pre"> </span>inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;</p><p style="text-align: left;">}</p><p style="text-align: left;">template<class T>void fwrit(const T x){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x<0)return (void)(putchar('-'),fwrit(-x));</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x>9)fwrit(x/10);putchar(x%10^48);</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">const int MAXN=2000;</p><p> </p><p style="text-align: left;">struct edge{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int to,nxt;</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge(){}</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge(const int T,const int N):to(T),nxt(N){}</p><p style="text-align: left;">}e[(MAXN<<1)+5];</p><p style="text-align: left;">int tail[MAXN+5],ecnt,siz[MAXN+5];</p><p style="text-align: left;">inline void add_edge(const int u,const int v){</p><p style="text-align: left;"><span style="white-space:pre"> </span>++siz[u],++siz[v];</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int N,minp;</p><p style="text-align: left;">int pt[MAXN+5];</p><p style="text-align: left;">int pre[MAXN+5][MAXN+5],nxt[MAXN+5][MAXN+5];</p><p style="text-align: left;">//这条边的 前驱,后继</p><p style="text-align: left;">int rt[MAXN+5][MAXN+5][2];</p><p style="text-align: left;">//点 u 的某一条边的 前根节点、后根节点</p><p style="text-align: left;">int len[MAXN+5][MAXN+5];</p><p style="text-align: left;">//这条边 所在链 的链表长度</p><p> </p><p style="text-align: left;">inline void init(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>qread(N);</p><p style="text-align: left;"><span style="white-space:pre"> </span>ecnt=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N)qread(pt[i]),tail[i]=siz[i]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N+1)rep(j,1,N+1)len[i][j]=pre[i][j]=nxt[i][j]=rt[i][j][0]=rt[i][j][1]=0;</p><p> </p><p style="text-align: left;"><span style="white-space:pre"> </span>int u,v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N-1){</p><p style="text-align: left;"><span style="white-space:pre"> </span>qread(u,v);</p><p style="text-align: left;"><span style="white-space:pre"> </span>add_edge(u,v);</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][v]=pre[v][u]=nxt[u][v]=nxt[v][u]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[u][v][0]=rt[u][v][1]=v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[v][u][0]=rt[v][u][1]=u;</p><p style="text-align: left;"><span style="white-space:pre"> </span>len[u][v]=len[v][u]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">void findPath(const int u,const int p){//当前节点、前一个节点</p><p style="text-align: left;"><span style="white-space:pre"> </span>int a=rt[u][p][0],b=rt[u][p][1],ta,tb;</p><p style="text-align: left;"><span style="white-space:pre"> </span>//a:来的边的前根 ; b:来的边的后根</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==N+1){//这是起点</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){//从哪条边起飞</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(ta!=v || (pre[u][p]==tb && len[u][ta]<siz[u]))</p><p style="text-align: left;"><span style="white-space:pre"> </span>//条件一:如果这条边已经有一个起点且不是自己</p><p style="text-align: left;"><span style="white-space:pre"> </span>//条件二:如果后面的那条边已经连接尾端, 且这条链的长度无法满足将所有边连起来</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;//那么就不能把 边{u,p} 与 边{u,v} 连在一起</p><p style="text-align: left;"><span style="white-space:pre"> </span>findPath(v,u);//否则可行</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==b){//如果 边{u,p} 的后面还暂时没有指定必须删哪一条边, 那么就可以考虑枚举一条边接在后面</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(pre[u][N+1]==0 && (nxt[u][N+1]!=a || len[u][a]==siz[u]))//则可以考虑在点 u 进行降落, 满足以下条件:</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果这个点的末删边还没有被指定(必须满足)</p><p style="text-align: left;"><span style="white-space:pre"> </span>//并且:</p><p style="text-align: left;"><span style="white-space:pre"> </span>//1.如果这条链接上开头,那么如果必须满足所有的边都在这条链上</p><p style="text-align: left;"><span style="white-space:pre"> </span>//2.如果没有接上开头,那么长度随意</p><p style="text-align: left;"><span style="white-space:pre"> </span>minp=Min(minp,u);//如果满足, 则 u 可以作为一个降落点</p><p> </p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){//假定 u 为一个中转点, 则再枚举一条边作为 边{u,p} 的出边,与其尾相连</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(a==ta || ta!=v || nxt[u][N+1]==v)//第一种大情况</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果这两条边已经在同一条链上</p><p style="text-align: left;"><span style="white-space:pre"> </span>//或者这个边不是一个起始边, 即枚举边的前面还有东西</p><p style="text-align: left;"><span style="white-space:pre"> </span>//或者枚举边是一条起飞边, 即保证它是所有对于 u 的边必须最先删除的边</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;//那么 当前 边{u,p} 都不能接在这条枚举边之上</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果这两条边分别属于这个点 最先删除、最后删除 的链表上的 尾、头</p><p style="text-align: left;"><span style="white-space:pre"> </span>//那么它们组合起来必须等于所有边的数量之和</p><p style="text-align: left;"><span style="white-space:pre"> </span>//否则, 这就是 提前自闭 的情况</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p> </p><p style="text-align: left;"><span style="white-space:pre"> </span>findPath(v,u);//如果以上都不满足, 那么这条边是合法的</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else findPath(nxt[u][p],u);//否则我们只能按照之前的规定访问这条边</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void merge(const int u,const int a,const int b){</p><p style="text-align: left;">//函数条件:以 a 所在的链表为前链表</p><p style="text-align: left;">//并且满足 a 是前链表尾, b 是后链表头</p><p style="text-align: left;"><span style="white-space:pre"> </span>int ta=rt[u][a][0],tb=rt[u][b][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>nxt[u][a]=b;</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][b]=a;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=ta;i && i!=N+1;i=nxt[u][i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>//访问链表的基本操作</p><p style="text-align: left;"><span style="white-space:pre"> </span>//更新每个点的前根、后根</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[u][i][0]=ta;</p><p style="text-align: left;"><span style="white-space:pre"> </span>rt[u][i][1]=tb;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>len[u][ta]+=len[u][b];</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">bool getMark(const int u,const int p){//还原路径, 并且给路径打上标记</p><p style="text-align: left;">//如果这条路径找到终点, 返回 1, 否则返回 0</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(u==minp){//如果找到了终点</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][N+1]=p;//把这条边设为最后删除的边</p><p style="text-align: left;"><span style="white-space:pre"> </span>nxt[u][p]=N+1;//并且把这条边的下一条边标记为 N+1, 表示这条边是最后删除的</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>int a=rt[u][p][0],b=rt[u][p][1],ta,tb;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==N+1){//这是起飞点</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(ta!=v || (pre[u][N+1]==tb && len[u][ta]<siz[u]))</p><p style="text-align: left;"><span style="white-space:pre"> </span>//如果枚举边前面有东西, 那么这肯定不能接在起始边的后面, 因为它前面已经有个什么 逼 了</p><p style="text-align: left;"><span style="white-space:pre"> </span>//或者是枚举边连接到末尾, 但是这条单链长度不够将所有的边包含到链里面</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;//那么这条边肯定不在路径上面, 可直接跳过</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(getMark(v,u)){//如果这就是正确的路径</p><p style="text-align: left;"><span style="white-space:pre"> </span>nxt[u][N+1]=v;//因为 u 点是起飞点, 所以把这条边记录为 u 的起飞边</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre[u][v]=N+1;//同时标记这条边的前驱, 与前面的 if 相互呼应(这不是语文...)</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else{//如果点 u 是中转点, 那么考虑枚举中转边</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(p==b){//如果这条边在链上后面没有其他边的时候</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=tail[u],v;i;i=e[i].nxt){</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=e[i].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ta=rt[u][v][0],tb=rt[u][v][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(a==ta || ta!=v || nxt[u][N+1]==v)//参考 findPath() 中相同位置的注释</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])//同样参考 findPath() 中同样位置</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(getMark(v,u)){</p><p style="text-align: left;"><span style="white-space:pre"> </span>merge(u,p,v);//把链表合并为一个</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else getMark(nxt[u][p],u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">signed main(){</p><p style="text-align: left;">#ifdef FILEOI</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("rdata.out","r",stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("file.out","w",stdout);</p><p style="text-align: left;">#endif</p><p style="text-align: left;"><span style="white-space:pre"> </span>int T=qread();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(T--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>init();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(N==1){</p><p style="text-align: left;"><span style="white-space:pre"> </span>writc(1,'\n');</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,1,N){</p><p style="text-align: left;"><span style="white-space:pre"> </span>minp=N+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>findPath(pt[i],N+1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>// printf("%d\n",minp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>getMark(pt[i],N+1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>writc(minp,' ');</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>putchar('\n');</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。