CF1396E——Distance Matching

传送门：QAQQAQ（题面翻译）

以后博客可能一直咕咕咕了。一些做题的思考可能会直接放在代码里而不是单独写博客，因为这样太浪费时间，只有一些比较新的题才会单独写博客

思路：对于这种构造可行解使得权值和恰好为某一值的题，一般都是先求出可以构造出来的最大和最小值，然后从某个极值按照一定方法进行连续修改

我们考虑每一条边对于答案的贡献：若边$E(u,v)$把数分成$U,V$两颗子树，则该边最大的贡献是$min(sz[U],sz[V])$，最小是$sz[U]\mod2$。

$min$太难处理，所以想一种办法把$min$去掉，通过重心的性质（每一个子树的$size$小于等于$\frac{n}{2}$），发现直接取重心就可以把$min$去掉了

所以就可以得到

$$minans=\sum_{i=1}^{n} [i \neq root]sz[i]\mod2$$

$$maxans=\sum_{i=1}^{n} [i \neq root]sz[i]$$

然后仔细想想会发现：答案有解的充要条件是$minans \leq k \leq maxans$且$(maxans-k)\mod2=0$

充分性：通过构造方法证明。

　　每次取在$size$最大的子树中选取两个$lca$深度最大的点，因为本来两个点都是向字树外连的，现在自己相连，所以$\Delta =2*dep[lca]$，然后删掉那两个点

　　容易发现这样构造是必定可以从$maxans$变成$minans$的，因为对于$sz[u]\mod2=0$的边，它底下肯定两两配对；对于$sz[u]\mod2=0$，这样的贪心会使得下面只有一个点向上经过它

　　因为点数始终为偶数，所以从最大子树删掉两个点以后不会使得次大子树的$size$大于$\frac{n}{2}$，上面求$minans,maxans$的式子始终成立

　　当最后一次$dep[lca]*2>rest$时，因为所有不是叶子节点的点都可以作$lca$，所以$dep$必定连续，即肯定能找到构造出刚好使得$rest=0$的方案。

　　剩下的点按照$max$的方案，跨子树分别连就可以了

必要性：因为$\Delta =2*dep[lca]$，所以如果不是$k,maxans$不是同奇同偶，一定无解

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=120000;

typedef long long ll;

typedef pair<int,int> pii;

#define mk make_pair

int n; ll k; vector<int> v[N];

int sz[N],dep[N],fa[N],root; ll minn=N,maxn=0;

void dfs1(int u,int f)

{

    sz[u]=1; int maxsz=0;

    for(int i=0;i<(int)v[u].size();i++)

    {

        int to=v[u][i]; if(to==f) continue;

        dfs1(to,u); sz[u]+=sz[to];

        maxsz=max(maxsz,sz[to]);

    }

    if(minn>max(maxsz,n-sz[u])) minn=max(maxsz,n-sz[u]),root=u;

}

int top[N],deg[N];

set<pii> S[N],R;//S维护子树中所有可能作为lca的点(即不是叶子)

void dfs(int u,int from)

{

    sz[u]=1;

    top[u]=from;

    if(from&&(int)v[u].size()-1>=1) S[from].insert(mk(dep[u],u));

    for(int i=0;i<(int)v[u].size();i++)

    {

        int to=v[u][i]; if(to==fa[u]) continue;

        if(u==root) from=to; deg[u]++;

        dep[to]=dep[u]+1; fa[to]=u;

        dfs(to,from); sz[u]+=sz[to];

    }

}

void del(int x)

{

    if(!--deg[fa[x]])

        S[top[x]].erase(mk(dep[fa[x]],fa[x]));

}

int vis[N];

vector<int> rem;

void dfs3(int u)

{

    if(!vis[u]) rem.push_back(u);

    for(int i=0;i<(int)v[u].size();i++)

    {

        int to=v[u][i]; if(to==fa[u]) continue;

        dfs3(to);

    }

}

int main()

{

    scanf("%d%lld",&n,&k);

    for(int i=1;i<n;i++)

    {

        int x,y; scanf("%d%d",&x,&y);

        v[x].push_back(y); v[y].push_back(x);

    }

    dfs1(1,-1); dep[root]=0; dfs(root,0);

    minn=0,maxn=0;

    for(int i=1;i<=n;i++)

        if(i!=root) maxn+=sz[i], minn+=sz[i]%2;

    if(k>maxn||k<minn||(maxn-k)&1) {puts("NO"); return 0;}

    puts("YES");

    for(int i=0;i<v[root].size();i++)

    {

        int to=v[root][i];

        if(sz[to]>1) R.insert(mk(sz[to],to));

    }

    ll rest=maxn-k;

    while(rest)

    {

        int now=R.rbegin()->second; R.erase(--R.end());

        int pos=S[now].rbegin()->second;

        if(2*dep[pos]>rest)

        {

            rest/=2;

            pos=S[now].lower_bound(mk(rest,0))->second;

            vector<int> V; V.clear();

            for(int i=0;i<(int)v[pos].size();i++)

            {

                int to=v[pos][i];

                if(to==fa[pos]||vis[to]) continue;

                V.push_back(to);

            }

            if((int)V.size()<2) V.push_back(pos);

            printf("%d %d\n",V[0],V[1]); vis[V[0]]=1; vis[V[1]]=1;

            rest-=dep[pos];

            break;

        }

        else

        {

            vector<int> V; V.clear();

            for(int i=0;i<(int)v[pos].size();i++)

            {

                int to=v[pos][i];

                if(to==fa[pos]||vis[to]) continue;

                V.push_back(to);

            }

            if((int)V.size()<2) V.push_back(pos);

            rest-=dep[pos]*2;

            printf("%d %d\n",V[0],V[1]); vis[V[0]]=1; vis[V[1]]=1;

            del(V[0]); del(V[1]);

        }

        sz[now]-=2;

        if(sz[now]>1) R.insert(mk(sz[now],now));

    }

    dfs3(root);

    int T=(int)rem.size()/2;

    for(int i=0;i<T;i++) printf("%d %d\n",rem[i],rem[i+T]);

    return 0;

}

巴特西

CF1396E——Distance Matching

最新文章

热门文章