300 iq contest 2 J Jiry Matchings【匹配】【凸包】【启发式合并】【树链剖分】

程序员文章站 2022-04-01 17:56:30

...

300iq牛逼！

题目大意

给出一棵树，边有边权，问 $k$ 条边的最大匹配 $(k\in[1,n))$ .
$n\le20w$

暴力做法一

首先暴力是很好想的， $dp[i][j][0/1]$ 表示 $i$ 号点的子树已经选了 $j$ 条边， $i$ 号点是否匹配时的答案，正常dp即可，复杂度为 $O(n^2)$ （注意不是 $O(n^3)$ 哦，然而也没卵用）。

暴力做法二

这题一眼看上去就很匹配的样子，所以直接上费用流，每次只增广一个流量即可。
复杂度为 $O(玄学)=O(不能过)$ .

题解

引理

首先要注意到一个事实：
若设 $f(k)$ 是选出k条边时的答案，则 $f(k)$ 是上凸的，即 $f(k+1)-f(k)\le f(k)-f(k-1)$ .
为什么？回忆暴力做法二，费用流每次增广一条路径的花费一定是单调的，对应到 $f(k)$ 中即答案的增量是单调的。

同理，若固定 $i$ 号点选或不选， $dp[i][j][0/1]$ 的值也是关于 $j$ 单调的.

开搞

回忆暴力做法一，本质上我们是要做一件这样的事情：

for (int i=0;i<sz[u];++i)
	for (int j=0;j<sz[v];++j)
		h[i+j]=max(h[i+j],f[i]+g[j]);

咋一看这好像只能 $O(n^2)$ 做，但引理告诉我们 $f[],g[]$ 都是上凸的，如果把 $f[],g[]$ 看成是凸包上的点 $(i,f[i]),(j,g[j])$ ，则 $h[]$ 是 $f[]$ 和 $g[]$ 的闵科夫斯基和（两个凸包的叠加），而求两个凸包的闵科夫斯基和是 $O(nlogn)$ 的！
由于这里的凸包比较特殊（相邻的点x差值为1），所以我们其实可以 $O(n)$ 完成上述运算，即：

for (int i=sz[u]-1;i>0;--i) f[i]-=f[i-1];
for (int j=sz[v]-1;j>0;--j) g[j]-=g[j-1];

int lf=1,lg=1,m=1;
h[0]=f[0]+g[0];
while (lf<sz[u]&&lg<sz[v])
	if (f[lf]>g[lg])
		h[m++]=f[lf++];
	else
		h[m++]=g[lg++];
while (lf<sz[u]) h[m++]=f[lf++];
while (lg<sz[v]) h[m++]=g[lg++];

for (int i=1;i<m;++i) h[i]+=h[i-1];

所以在 $dp$ 时，合并两个儿子的复杂度时 $O(sz[u]+sz[v])$ 的，虽然相较原暴力做法已经很好了，但复杂度还是接近 $O(n^2)$ ，依然不能AC。

这个时候就需要用到启发式合并的思想：我们先把一个节点的所有轻儿子合并在一起，然后再把一条重链上的所有节点合并在一起，则由树剖的性质可知复杂度为 $O(合并复杂度*log)$ 。

而此时合并变成了多个数组合并，类似于线段树/倍增那样合并即可，单次合并复杂度为 $O(sz*\log sz)$ .

所以最后这题的复杂度为 $O(nlog^2n)$ ，当然细节还是有那么一点的.

300iq牛逼！

#include<bits/stdc++.h>
#define maxn 200050
using namespace std;
typedef long long LL;

const LL inf=1LL<<60;

int n;

int tot;
LL cost[maxn<<1];
int head[maxn],edge[maxn<<1],nxt[maxn<<1];

void join(int u,int v,int w)    {
    cost[tot]=w; edge[tot]=v; nxt[tot]=head[u]; head[u]=tot++;
    cost[tot]=w; edge[tot]=u; nxt[tot]=head[v]; head[v]=tot++;
}

int sz[maxn];
int fa[maxn],son[maxn];

int val[maxn];
vector<LL> f[2][maxn];

vector<LL> g[2][2][maxn];

vector<LL> merge(vector<LL> a,vector<LL> b)   {
    if (!a.size()) return b;
    if (!b.size()) return a;

    for (size_t i=a.size()-1;i;--i)    a[i]-=a[i-1];
    for (size_t i=b.size()-1;i;--i)    b[i]-=b[i-1];
    vector<LL> res(1,a.front()+b.front());
    size_t l=1,r=1;
    while (l<a.size()&&r<b.size())  {
        if (a[l]>b[r])
            res.push_back(a[l++]);
        else
            res.push_back(b[r++]);
    }
    while (l<a.size())  res.push_back(a[l++]);
    while (r<b.size())  res.push_back(b[r++]);

    for (size_t i=1;i<res.size();++i)
        res[i]+=res[i-1];
    return res;
}

vector<LL> shift(const vector<LL> &a,LL x)   {
    vector<LL> res;
    res.push_back(-inf);
    for (size_t i=0;i<a.size();++i)
        res.push_back(a[i]+x);
    return res;
}

vector<LL> max(const vector<LL>& a,const vector<LL>& b)    {
    vector<LL> res(max(a.size(),b.size()));
    for (size_t i=0;i<res.size();++i)  {
        res[i]=-inf;
        if (i<a.size()) res[i]=max(res[i],a[i]);
        if (i<b.size()) res[i]=max(res[i],b[i]);
    }
    return res;
}

void mergeLink(int i)   {
    vector<int> s;
    for (;i;i=son[i])
        s.push_back(i);
    for (size_t i=0;i<s.size();++i) 
        for (int c:{0,1})   {
            g[c][c][i]=f[c][s[i]];
            g[c][c^1][i]=vector<LL>{-inf};
        }
    for (size_t len=2;len/2<=s.size();len<<=1)
        for (size_t i=0;i+len/2<s.size();i+=len) {
            vector<LL> res[2][2];
            for (int a:{0,1})
                for (int d:{0,1})
                    for (int b:{0,1})
                        for (int c:{0,1})   {
                            vector<LL> t=merge(g[a][b][i],g[c][d][i+len/2]);
                            int _a=a,_d=d;
                            
                            res[a][d]=max(res[a][d],t);
                            if (!b&&!c) {
                                if (len/2==1)   _a=1;
                                if (len/2==1||i+len/2==s.size()-1)  _d=1;
                                t=shift(t,val[s[i+len/2]]);
                                res[_a][_d]=max(res[_a][_d],t);
                            }

                        }
            for (int a:{0,1})
                for (int b:{0,1})
                    g[a][b][i]=res[a][b];
        }
}

vector<LL> h[2][maxn];

void mergeSon(int i)    {
    vector<int> s;
    for (int k=head[i];~k;k=nxt[k]) {
        int j=edge[k];
        if (fa[i]==j||son[i]==j) continue;
        s.push_back(j);
    }

    h[0][0]=vector<LL>{0},h[1][0]=vector<LL>{-inf};
    for (size_t i=0;i<s.size();++i)    {
        mergeLink(s[i]);
        h[0][i]=vector<LL>{0},h[1][i]=vector<LL>{-inf};
        for (int a:{0,1})  {
            for (int b:{0,1})   {
                h[0][i]=max(h[0][i],g[a][b][0]);
                if (!a) {
                    h[1][i]=max(h[1][i],shift(g[a][b][0],val[s[i]]));
                }
            }
        }
    }

    for (size_t len=2;len/2<=s.size();len<<=1)   {
        for (size_t i=0;i+len/2<s.size();i+=len)   {
            vector<LL> res[2];
            for (int a:{0,1})   
                for (int b:{0,1})   {
                    if (a&&b) continue;
                    vector<LL> t=merge(h[a][i],h[b][i+len/2]);
                    res[a|b]=max(res[a|b],t);
                }
            for (int c:{0,1})
                h[c][i]=res[c];
        }
    }

    for (int c:{0,1})
        f[c][i]=h[c][0];
}

int dfs(int i)  {
    for (int k=head[i];~k;k=nxt[k]) {
        int j=edge[k];
        if (fa[i]==j) continue;
        fa[j]=i;
        sz[i]+=dfs(j);
        val[j]=cost[k];
        if (sz[son[i]]<sz[j])
            son[i]=j;
    }
    mergeSon(i);
    return ++sz[i];
}

int main()  {
    memset(head,-1,sizeof(head));

    scanf("%d",&n);
    for (int k=1;k<n;++k)   {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        join(u,v,w);
    }

    dfs(1);

    mergeLink(1);
    vector<LL> res;
    for (int a:{0,1})
        for (int b:{0,1})
            res=max(res,g[a][b][0]);
    for (int i=1;i<n;++i)
        if (i<(int)res.size())
            printf("%lld ",res[i]);
        else
            printf("? ");

    return 0;
}