[NC记录]AT3968 [AGC025E] Walking on a Tree

**题意** ： 给出一棵 $n$ 个点的树以及 $m$ 条树上简单路径。 要求给简单路径定向。定向后，树边 $u,v$ 的边权定义为 ： - 边权初始为 $0$。 - 若**存在**某条路径以 $u\rightarrow v$ 的方式经过，边权加一。 - 若**存在**某条路径以 $v\rightarrow u$ 的方式经过，边权加一。 - 最终的边权可能为 $0,1,2$。 最大化边权和。求出这个最大值，并给出定向方案。 $n,m\leq 2000$ ，时限$\texttt{2s}$。 ------------ > 感谢 @Kinandra 大神的指导。 对于第 $i$ 条边，记其被路径经过的次数为 $c_i$ ，则这条边的权值上界为 $\min\{2,c_i\}$。 猜想存在一种方案使得每条边的权值均达到上界。 考虑某个叶节点 $u$ 与连接该叶节点的唯一的边（编号为 $i$）。 若 $c_i=0$ ，直接将 $u$ 与该边删除。 若 $c_i=1$ ，存在恰好一条路径的端点为 $u$ ，将其更改为 $v$（这条路径一定经过边 $i$ 一次，方向则不关心）。然后将 $u$ 与该边删除。 若 $c_i\geq 2$ ，则要安排一条从里到外的路径和一条从外到里的路径。 任选两条经过边 $i$ 的路径 $(u,a),(u,b)$ ，定向为 $(u\rightarrow a),(b\rightarrow u)$ 或者 $(a\rightarrow u),(u\rightarrow b)$。 两种方案对应下图 ：  记两条路径的的分叉点为 $t$ ，不难发现，路径 $(u,t)$ 上的边都被正反经过各一次，完成指标。 而 $(a,t),(b,t)$ 上的边要么方向是 $(a\rightarrow t),(t\rightarrow b)$，要么是 $(b\rightarrow t),(t\rightarrow a)$ ，不难发现，这等价于（可以自由选择方向的）路径 $(a,b)$。 于是，我们将 $(u,d)$ 上的边设为“已完成”（这可以暴力）。然后删去路径 $(u,a),(u,b)$ ，并加入路径 $(a,b)$。 对于其他端点为 $u$ 的路径，将 $u$ 改成 $v$。最后将 $u$ 与该边删除。 - 还要说明一下我们没有破坏 $c_i$ 的前提条件。 对于 $(u,d)$ 上的边，$c$ 减少了 $2$ ，但他们的贡献已经达到上界，不用再考虑。 对于 $(a,b)$ 上的边， $c$ 没有变化。其他边的 $c$ 也显然不变。 于是，根据归纳法，该算法总能找到符合要求的解。 具体实现时，随意指定一个节点作为根，按照后续遍历删除节点。 处理节点 $v$ 的返祖边时，需要尝试找出两条一段在 $v$ 子树内一段不在的路径，可以使用 `std::set` 维护。 若找不到只能找到一条，则不操作路径。 若找到两条，则将它们打上删除标记。并新加入一条路径，表示不重合部分的决策。 （注意这条新路径的决策会影响两条旧路径的决策，在最终回答问题时需要推算决策） 然后将重合部分的链打上标记，标记了的边自动获得 $2$ 的满贡献。这可以用树状数组链加实现。 复杂度为 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #include<set> #define Pr pair<int,int> #define mp make_pair #define fir first #define sec second #define Itor set<Pr>::iterator #define pb push_back #define MaxN 2050 using namespace std; vector<int> g[MaxN]; struct Path{int u,v,f;bool vis;}l[MaxN<<1]; int n,m,f[10][MaxN],dep[MaxN],tim,dfn[MaxN],out[MaxN]; void pfs(int u) { dfn[u]=++tim; for (int i=0,v;i<g[u].size();i++) if (!dep[v=g[u][i]]){ dep[v]=dep[f[0][v]=u]+1; pfs(v); } out[u]=tim; } int lca(int u,int v) { if (dep[u]<dep[v])swap(u,v); int k=9; while(k--)while(dep[f[k][u]]>=dep[v])u=f[k][u]; if (u==v)return u; k=9;while(k--)while(f[k][u]!=f[k][v]) {u=f[k][u];v=f[k][v];} return f[0][u]; } #define lbit(p) (p&-p) struct SumDS { int t[MaxN]; void add(int p,int c) {while(p<=n){t[p]+=c;p+=lbit(p);}} int qry(int p){ int ret=0; while(p){ret+=t[p];p^=lbit(p);} return ret; } }T; void padd(int u,int v) {T.add(dfn[u],1);T.add(dfn[v],1);T.add(dfn[lca(u,v)],-2);} int subqry(int u) {return T.qry(out[u])-T.qry(dfn[u]-1);} int ans,o[MaxN]; set<Pr> s; void dfs(int u) { for (int i=0,v;i<g[u].size();i++) if (dep[v=g[u][i]]>dep[u]){ dfs(v); if (subqry(v)>0){ans+=2;continue;} Itor itl=s.lower_bound(mp(dfn[v],0)) ,itr=s.upper_bound(mp(out[v]+1,0)); int p1=0,p2=0; while(itl!=itr&&!p2){ Itor sav=itl++; int p=sav->sec; if (l[p].vis||(dfn[v]<=dfn[l[p].u]&&dfn[l[p].v]<=out[v])) s.erase(sav); else {if (!p1)p1=p;else p2=p;} }if (p1)ans++;if (p2)ans++; if (p1&&p2){ l[p1].vis=l[p2].vis=1; int a=(dfn[v]<=dfn[l[p1].u]&&dfn[l[p1].u]<=out[v]) ? l[p1].v : l[p1].u ,b=(dfn[v]<=dfn[l[p2].u]&&dfn[l[p2].u]<=out[v]) ? l[p2].v : l[p2].u; if (a==b){ if (l[p1].u==l[p2].u||l[p1].v==l[p2].v)swap(l[p1].u,l[p1].v); padd(u,a); }else { int t=lca(a,b),t2=lca(v,a),t3=lca(v,b); if (dep[t]<dep[t2])t=t2;if (dep[t]<dep[t3])t=t3; padd(u,t); if (dfn[a]>dfn[b])swap(a,b); l[l[p1].f=l[p2].f=++m]=(Path){a,b}; s.insert(mp(dfn[a],m));s.insert(mp(dfn[b],m)); } } } } int main() { scanf("%d%d",&n,&m); for (int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); g[u].pb(v);g[v].pb(u); } dep[1]=1;pfs(1); for (int i=1;i<=m;i++){ scanf("%d%d",&l[i].u,&l[i].v); if (dfn[l[i].u]>dfn[l[i].v])swap(l[i].u,l[i].v); s.insert(mp(dfn[l[i].u],i));s.insert(mp(dfn[l[i].v],i)); } for (int j=1;j<9;j++) for (int i=1;i<=n;i++) f[j][i]=f[j-1][f[j-1][i]]; int m0=m; dfs(1); printf("%d\n",ans); for (int i=m;i;i--) if (l[i].f&&(l[l[i].f].u==l[i].v||l[l[i].f].v==l[i].u)) swap(l[i].u,l[i].v); for (int i=1;i<=m0;i++) printf("%d %d\n",l[i].u,l[i].v); return 0; } ```