【洛谷8341】[AHOI2022] 回忆

· · 题解

一个 O(n+m) 的解法？

称一条路径的 目标深度 为要满足分配给它的点对的限制至少需要达到的深度。

对于已经完成目标的路径，将直的路径（即一个端点是另一个端点的祖先的路径）称作 尚未匹配的路径，两条拼接在一起的直的路径称作 完成匹配的路径对。

考虑一个点子树内的信息，可以表示成若干个完成匹配的路径对、若干条尚未匹配的路径、若干条尚未完成目标的路径。

其中，对于尚未匹配的路径，我们能匹配就先匹配掉，因为已经完成的匹配之后可以拆，而现在没有匹配以后就不知道能不能匹配了。

如果有多条尚未完成目标的路径，我们只需保留一条路径继续做匹配，剩余的路径完成当前的任务就可以收工了。而保留的那条路径一定是 目标深度最小 的路径，所以对于其余尚未完成目标的路径可以直接在对应深度打标记表示到了那时会多出一条完成任务的 尚未匹配的路径。

先是对于边界情况，注意到几个结论：

然后再去考虑两个子树 X,Y 信息的贪心合并：

于是就做完了？时间复杂度 O(n+m)，代码也很好写。

不知道上面的过程会不会有什么问题，万一把我叉掉了通知我一下......

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 200000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
namespace FastIO
{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int n,m,ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];
int D[N+5];void dfs(CI x,CI lst=0)//预处理深度
{
    for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(D[e[i].to]=D[x]+1,dfs(e[i].to,x),0);
}
int a[N+5],b[N+5],mn[N+5],g[N+5],h[N+5];void Solve(CI x,CI lst=0)
{
    for(RI i=lnk[x],y;i;i=e[i].nxt) if((y=e[i].to)^lst)
    {
        if(Solve(y,x),b[y]+=h[D[x]],h[D[x]]=0,!a[y]&&!b[y]&&!mn[y]) continue;//子树为空，无需合并
        mn[y]==D[x]&&(++b[y],mn[y]=0);//完成了目标
        if(mn[x]&&mn[y]) mn[x]<mn[y]?++h[mn[y]]:(++h[mn[x]],mn[x]=mn[y]);else mn[x]|=mn[y];//合并尚未完成目标的路径
        if(b[x]>b[y]) swap(a[x],a[y]),swap(b[x],b[y]);//让y尚未匹配的路径数较大
        if(2*a[x]+b[x]>=b[y]) a[x]=a[x]+a[y]+(b[x]+b[y]>>1),b[x]=(b[x]+b[y])&1;//能匹配完
        else b[y]-=2*a[x]+b[x],a[x]=2*a[x]+b[x]+a[y],b[x]=b[y];//匹配不完
    }
    if(g[x]) mn[x]?mn[x]=min(mn[x],g[x]):(mn[x]=g[x],b[x]?--b[x]:a[x]&&(--a[x],++b[x]));//处理当前点上的要求
}
int main()
{
    RI Tt,i,x,y;read(Tt);W(Tt--)
    {
        for(read(n,m),ee=0,i=1;i<=n;++i) lnk[i]=a[i]=b[i]=g[i]=mn[i]=0;
        for(i=1;i^n;++i) read(x,y),add(x,y),add(y,x);D[1]=1,dfs(1);
        for(i=1;i<=m;++i) read(x,y),g[y]=g[y]?min(g[y],D[x]):D[x];//在y处记录要求
        Solve(1),writeln(a[1]+b[1]);
    }return clear(),0;
}