uoj388 【UNR #3】配对树

谁借莪１个温暖的怀抱￠ 2023-10-11 05:16 0阅读 0赞

[题目][Link 1]

看起来啥都不会

先来思考那个子问题，给出\\(2\\times k\\)个树上关键点，让这些关键点两两匹配，使得\\(k\\)对匹配的边权和最小

不妨考虑树上差分，众所周知，让路径\\((x,y)\\)上边权加\\(1\\)只需要另\\(x,y\\)点权加\\(1\\)，\\(\\rm LCA(x,y)\\)点权减\\(2\\)，再求一下子树和即可

先将\\(2\\times k\\)个关键点的点权都加\\(1\\)，现在我们需要选择\\(k\\)个\\(\\rm LCA\\)，让这些\\(\\rm LCA\\)的点权都减\\(2\\)，由于我们最后需要最小化所有被经过的边权和，于是我们需要让这些\\(\\rm LCA\\)尽可能地深

设\\(d\_x\\)表示点\\(x\\)子树内部有多少个关键点，显然\\(d\_x=\\sum\_\{v\\in son(x)\}d\_v\\)，**我们让这些关键点两两匹配，就形成了\\(\\left \\lfloor \\frac\{d\_x\}\{2\} \\right \\rfloor\\)组匹配，于是我们让\\(x\\)点权减去\\(2\\times \\left \\lfloor \\frac\{d\_x\}\{2\} \\right \\rfloor\\)，同时\\(d\_x\\)也会变成\\(d\_x-2\\times \\left \\lfloor \\frac\{d\_x\}\{2\} \\right \\rfloor\\)即\\(d\_x\\rm mod\\ 2\\)**

**于是\\(d\_v\\)也只可能是\\(0\\)或\\(1\\)**，即一个儿子最多也只能上传给父亲一个未匹配的关键点，所以并不会出现在\\(x\\)处匹配的\\(\\rm LCA\\)不是\\(x\\)的情况

得出所有点的点权之后，做一遍子树和即得到了每一条边被经过的次数，我们就能计算最小匹配了

暴力枚举所有长度为偶数的区间，于是我们得到了一个\\(O(m^2n)\\)的优秀做法

考虑一下这个算法带来的启示

首先一条边被经过的次数一定不会超过\\(1\\)，可以考虑对于每一条边计算出其再多少个区间里被经过

同时还由于每一个点的\\(d\\)只可能是\\(0\\)或\\(1\\)，当\\(d\_x=0\\)时，就说明\\(x\\)内的关键点在\\(x\\)子树内部就已经匹配完了，不需要和\\(x\\)外面的关键点匹配了；当\\(d\_x=1\\)时，说明\\(x\\)子树内部有一个未匹配的关键点，**由于这个关键点一定要和\\(x\\)子树外的点匹配，所以\\(x\\)到其父亲的那一条边一定会被经过**

显然\\(d\_x\\)即\\(x\\)子树内部关键点个数的奇偶性，于是**当一个点子树内部有奇数个关键点时，这个点到其父亲的边一定会被经过**

现在我们只需要对于每个点，求出有多少个长度为偶数的区间，使得其子树内部有奇数个关键点

我们可以大力\\(\\rm dsu\\ on\\ tree\\)，对于每一个点求出一个桶\\(tax\\)，\\(tax\_i\\)表示给出序列上的第\\(i\\)个点是否在这个点的子树内部出现过

现在我们只需要求这个桶有多少个长度为偶数的区间异或和为\\(1\\)即可

考虑对这个桶做一遍前缀异或和，\\(\[l,r\]\\)区间长度为偶数且异或和为\\(1\\)需要满足，\\(r-l+1\\equiv 0(\\rm mod\\ 2),pre\_r-pre\_\{l-1\}\\equiv 1(\\rm mod \\ 2)\\)，即\\(l-1\\)和\\(r\\)的奇偶性相同，\\(pre\_r\\)和\\(pre\_\{l-1\}\\)的奇偶性不同

于是我们开两棵线段树，分别维护奇位置和偶位置的前缀异或和，单点修改变成了后缀取反，线段树随便维护一下就可以了，复杂度\\(O(n\\log^2n)\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    const int mod=998244353;
    const int maxn=1e5+5;
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    std::vector<int> v[maxn];
    struct E{int v,nxt,w;}e[maxn<<1];
    int deep[maxn],sum[maxn],fa[maxn],son[maxn],id[maxn],head[maxn];
    int n,m,num,s[2],ans,S;
    inline void add(int x,int y,int z) {
        e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=z;
    }
    struct Segment_Tree {
        int l[maxn<<1],r[maxn<<1],tag[maxn<<1],g[maxn<<1],len[maxn<<1],cl[maxn<<1];
        void build(int x,int y,int i) {
            l[i]=x,r[i]=y;len[i]=r[i]-l[i]+1;
            if(x==y) return;
            int mid=x+y>>1;
            build(x,mid,i<<1),build(mid+1,y,i<<1|1);
        }
        inline void pushdown(int i) {
            if(cl[i]) {
                cl[i]=0;cl[i<<1]=cl[i<<1|1]=1;
                g[i<<1|1]=g[i<<1]=tag[i<<1]=tag[i<<1|1]=0;
            }
            if(!tag[i]) return;tag[i]=0;
            tag[i<<1]^=1;tag[i<<1|1]^=1;
            g[i<<1]=len[i<<1]-g[i<<1];
            g[i<<1|1]=len[i<<1|1]-g[i<<1|1];
        }
        void change(int pos,int i) {
            if(l[i]>=pos) {
                g[i]=len[i]-g[i];
                tag[i]^=1;return;
            }
            pushdown(i);
            int mid=l[i]+r[i]>>1;
            change(pos,i<<1|1);
            if(pos<=mid) change(pos,i<<1);
            g[i]=g[i<<1]+g[i<<1|1];
        }
        inline void clear() {cl[1]=1;g[1]=tag[1]=0;}
    }T[2];
    void dfs1(int x) {
        sum[x]=1+v[x].size();
        for(re int i=head[x];i;i=e[i].nxt) {
            if(deep[e[i].v]) continue;
            deep[e[i].v]=deep[x]+1;dfs1(e[i].v);
            sum[x]+=sum[e[i].v];
            fa[e[i].v]=(e[i].w>=mod?e[i].w-mod:e[i].w);
            if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;
        }
    }
    void calc(int pos) {
        T[pos&1].change(id[pos],1);
        if(pos<m) T[(pos+1)&1].change(id[pos+1],1);
    }
    void solve(int x) {
        for(re int i=0;i<v[x].size();i++) 
            calc(v[x][i]);
        for(re int i=head[x];i;i=e[i].nxt) {
            if(deep[e[i].v]<deep[x]||e[i].v==S) continue;
            solve(e[i].v);
        }
    }
    void dfs(int x,int k) {
        for(re int i=head[x];i;i=e[i].nxt) 
        if(son[x]!=e[i].v&&deep[e[i].v]>deep[x]) dfs(e[i].v,0);
        if(son[x]) dfs(son[x],1),S=son[x];
        solve(x);int now=0;
        now=1ll*T[0].g[1]*(s[0]-T[0].g[1])%mod;
        now=(now+1ll*T[1].g[1]*(s[1]-T[1].g[1])%mod)%mod;
        ans=(ans+1ll*now*fa[x]%mod)%mod;
        if(!k) T[0].clear(),T[1].clear();
    }
    int main() {
        n=read();m=read();
        for(re int x,y,z,i=1;i<n;i++) {
            x=read(),y=read(),z=read();
            add(x,y,z),add(y,x,z);
        }
        s[0]=s[1]=0;if(m==1) {puts("0");return 0;}
        for(re int i=1;i<=m;i++) id[i]=++s[i&1];
        T[0].build(1,s[0],1),T[1].build(1,s[1],1);s[0]++;
        for(re int x,i=1;i<=m;i++) x=read(),v[x].push_back(i);
        deep[1]=1,dfs1(1),dfs(1,1);
        printf("%d\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11475573.html

[Link 1]: http://uoj.ac/contest/45/problem/388