ZROI Contest 350

July 26, 2019

1045views

4855 words

现在有一棵树要求对于每个点 $x$ ,求所有点到他的链的最大点权之和
$n \leq 4 \times 10^5$

题解：又是我不会的思博题。
这种题目我们可以首先考虑在链上的做法：
显然有一种基于分治的方法，但是很难扩展到树上。
所以我们考虑如果变成边权是不是好维护。。（
我们考虑定义点 $i$ 和 $i+1$ 之间的边的边权是 $max\{a_{i},a_{i+1}\}$。然后变成了求两点之间边权最大值。我们考虑将边从小到大排序，每次加入一条新边，对于边左端点的连通块，答案都会加上一个边权乘右边端点连通块的大小。右面答案贡献同理。
所以我们如果放在树上也是差不多做。可以维护处所有连通块的大小，然后每次加边相当于是一个子树加贡献操作。
我们如果直接并查集路径压缩就会自闭。我们必须要维护出树的形态。第一种情况是使用带权并查集。注意要额外减去合并时多余的贡献。
一个更简单的做法是使用重构树：这样我们直接在点上打标记就可以了

/*
 * Author: RainAir
 * Time: 2019-07-26 15:20:25
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1e6 + 5;
std::vector<int> G[MAXN];

struct Edge{
    int u,v,w;

    bool operator < (const Edge &t) const {
        return w < t.w;
    }
}e[MAXN];
int n;
int p[MAXN],v[MAXN],f[MAXN],sm[MAXN],sz[MAXN],val[MAXN],cnt;

inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline void merge(int x,int y){
    int fx = find(x),fy = find(y);
    G[++cnt].pb(fx);G[cnt].pb(fy);
    G[fx].pb(cnt);G[fy].pb(cnt);
    f[fx] = f[fy] = cnt;
    sz[cnt] = sz[fx]+sz[fy];
}

int ans[MAXN];

inline void dfs(int v,int fa=0,int sum=0){
    sum += sm[v];ans[v] = sum;
    for(auto x:G[v]){
        if(x == fa) continue;
        dfs(x,v,sum);
    }
}

signed main(){
    scanf("%lld",&n);cnt = n;
    FOR(i,2,n) scanf("%lld",p+i);
    FOR(i,1,n) scanf("%lld",val+i);
    std::fill(sz,sz+n+1,1);
    FOR(i,2,n) e[i-1] = (Edge){i,p[i],std::max(val[p[i]],val[i])};
    std::sort(e+1,e+n);FOR(i,1,2*n) f[i] = i;
    FOR(i,1,n-1){
        int u = e[i].u,v = e[i].v,w = e[i].w;
        int fu = find(u),fv = find(v);
        sm[fu] += sz[fv]w;sm[fv] += sz[fu]w;
        merge(fu,fv);
    }
    int rt = find(1);
    dfs(rt);
    FOR(i,1,n) printf("%lld ",ans[i]+val[i]);puts("");
    return 0;
}

遇到这种删数的问题我们可以首先考虑最后一个删除的数是什么/对答案的影响。
发现如果我们钦定删除了某一个点，它的值是 $x$，那么这个点会将当前区间分裂成两个区间，并且要保证左区间删除的时候不能有一时刻最右边的点的值为 $x$，右边区间同理。
所以我们可以考虑设计出一个区间 dp：$f_{l,r,lk,rk}$ 表示删除区间 $l,r$，强制不让某一时刻的左边为 $lk$,也不让某一时刻右边为 $rk$.转移显然：
$$f_{l,r,lk,rk} = \sum_{k = l}^r \left(^{r-l}_ {k-l}\right)f_{l,k-1,lk,a_k}\times f_{k+1,r,a_k,rk}$$
总共是 $O(n^5)$ 的。
转移发现 $lk = a_{l-1},rk = a_{r+1}$，所以变成 $O(n^3)$。

/*
 * Author: RainAir
 * Time: 2019-07-26 16:04:47
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1000+5;
const int ha = 998244353;
int fMAXN;
int n,a[MAXN];
int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%ha;
        a = 1llaa%ha;
        n >>= 1;
    }
    return res;
}

inline void init(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1llfac[i-1]i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1llinv[i+1](i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    return 1llfac[n]inv[m]%ha*inv[n-m]%ha;
}

signed main(){
    init();
    scanf("%lld",&n);FOR(i,1,n) scanf("%lld",a+i);
    FOR(i,2,n){
        if(a[i] == a[i-1]){
            puts("0");return 0;
        }
    }
    FOR(i,1,n) fi = 1;
    FOR(i,1,n+1) fi = 1;
    a[0] = a[n+1] = -1;
    FOR(len,2,n){
        FOR(l,1,n){
            int r = l+len-1;
            if(r > n) break;
            FOR(k,l,r){
                if(a[k] != a[l-1] && a[k] != a[r+1])
                    (fl += 1llflfk+1%ha*C(r-l,k-l)) %= ha;
            }
        }
    }
    printf("%lldn",f1);
    return 0;
}

ZROI Contest 350

RainAir • 2019 年 07 月 26 日

现在有一棵树要求对于每个点 $x$ ,求所有点到他的链的最大点权之和
$n \leq 4 \times 10^5$

/*
 * Author: RainAir
 * Time: 2019-07-26 15:20:25
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1e6 + 5;
std::vector<int> G[MAXN];

struct Edge{
    int u,v,w;

    bool operator < (const Edge &t) const {
        return w < t.w;
    }
}e[MAXN];
int n;
int p[MAXN],v[MAXN],f[MAXN],sm[MAXN],sz[MAXN],val[MAXN],cnt;

inline int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

inline void merge(int x,int y){
    int fx = find(x),fy = find(y);
    G[++cnt].pb(fx);G[cnt].pb(fy);
    G[fx].pb(cnt);G[fy].pb(cnt);
    f[fx] = f[fy] = cnt;
    sz[cnt] = sz[fx]+sz[fy];
}

int ans[MAXN];

inline void dfs(int v,int fa=0,int sum=0){
    sum += sm[v];ans[v] = sum;
    for(auto x:G[v]){
        if(x == fa) continue;
        dfs(x,v,sum);
    }
}

signed main(){
    scanf("%lld",&n);cnt = n;
    FOR(i,2,n) scanf("%lld",p+i);
    FOR(i,1,n) scanf("%lld",val+i);
    std::fill(sz,sz+n+1,1);
    FOR(i,2,n) e[i-1] = (Edge){i,p[i],std::max(val[p[i]],val[i])};
    std::sort(e+1,e+n);FOR(i,1,2*n) f[i] = i;
    FOR(i,1,n-1){
        int u = e[i].u,v = e[i].v,w = e[i].w;
        int fu = find(u),fv = find(v);
        sm[fu] += sz[fv]w;sm[fv] += sz[fu]w;
        merge(fu,fv);
    }
    int rt = find(1);
    dfs(rt);
    FOR(i,1,n) printf("%lld ",ans[i]+val[i]);puts("");
    return 0;
}

/*
 * Author: RainAir
 * Time: 2019-07-26 16:04:47
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1000+5;
const int ha = 998244353;
int fMAXN;
int n,a[MAXN];
int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%ha;
        a = 1llaa%ha;
        n >>= 1;
    }
    return res;
}

inline void init(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1llfac[i-1]i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1llinv[i+1](i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    return 1llfac[n]inv[m]%ha*inv[n-m]%ha;
}

signed main(){
    init();
    scanf("%lld",&n);FOR(i,1,n) scanf("%lld",a+i);
    FOR(i,2,n){
        if(a[i] == a[i-1]){
            puts("0");return 0;
        }
    }
    FOR(i,1,n) fi = 1;
    FOR(i,1,n+1) fi = 1;
    a[0] = a[n+1] = -1;
    FOR(len,2,n){
        FOR(l,1,n){
            int r = l+len-1;
            if(r > n) break;
            FOR(k,l,r){
                if(a[k] != a[l-1] && a[k] != a[r+1])
                    (fl += 1llflfk+1%ha*C(r-l,k-l)) %= ha;
            }
        }
    }
    printf("%lldn",f1);
    return 0;
}

ZROI Contest 350

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

Splay 学习笔记 · 续

CF 1312 题解

contest1 题解

「P5163」WD与地图

CF1525F Goblins And Gnomes

ZROI Contest 350