20zr联赛集训day17

Author： RainAir
发布时间：November 3, 2020
857views
No comments
1023 words
Categories：题解

B 被降智了，所以掉分了。

A

考虑将这个串拆成三部分考虑：114，5，14。

设 $f_{i,j}$ 表示 114 的 $4$ 的位置是 $i$，1 代表 $j$ 的方案数，$g_{i,j}$ 表示 14 中 1 的位置是 $i$，4 代表 $j$ 的方案数，另外记录一个 $s_{i,j}$ 表示前 $i$ 个字符中 $j$ 的数量，字符串是 $a$，那么答案是：

$$ \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times (j-i-1-(s_{j-1,a_i}-s_{i,a_i})-(s_{j-1,a_j}-s_{i,a_j})) $$

我们考虑将这个式子拆成可以分开维护的形式：

$$ \begin{aligned} \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(j-1-s_{j-1,a_i}-s_{j-1,a_j})\\ +\sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(-i+s_{i,a_i}+s_{i,a_j})\\ \end{aligned} $$

我们枚举 $i$ 和 $a_j$，维护对应的 $\sum g_{j,a_i}\times (j-1-s_{j-1,a_i}-s_{j-1,a_j})$ 和 $\sum g_{j,a_i}$ 即可。

可以用一些滚动数组技巧做到空间 $O((\Sigma) ^2)$。放个卡完空间的代码：

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#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(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;
const int ha = 114514;
char str[MAXN];
int n;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int sm1[26][26],sm2[26][26];
int smf[26],smg[26];

int main(){
    scanf("%s",str+1);n = strlen(str+1);
    auto f = [&](int i,int j){
        return str[i]-'a' == j ? 0 : (1ll*smf[j]*(smf[j]-1)/2)%ha;
    };
    auto g = [&](int i,int j){
        return str[i]-'a' == j ? 0 : smg[j];
    };
    int ans = 0;
    FOR(i,1,n-1) add(smf[str[i]-'a'],1);
    ROF(i,n,1){
        FOR(j,0,25){
            if(str[i]-'a' == j) continue;
            add(ans,1ll*f(i,j)*sm2[j][str[i]-'a']%ha);
            int coe = (smf[j]+smf[str[i]-'a']+1-i+ha)%ha;
            coe = 1ll*coe*f(i,j)%ha;
            add(ans,1ll*coe*sm1[j][str[i]-'a']%ha);
        }
        FOR(j,0,25){
            add(sm1[str[i]-'a'][j],g(i,j));
            int coe = (i-1-smf[j]-smf[str[i]-'a']+ha+ha)%ha;
            add(sm2[str[i]-'a'][j],1ll*g(i,j)*coe%ha);
        }
        if(i-1) add(smf[str[i-1]-'a'],ha-1);
        add(smg[str[i]-'a'],1);
    }
    printf("%d\n",ans);
    return 0;
}

B

这个题没有括号！！表达式求值没有括号要考虑按照某个运算分成若干块处理。

我们按照或运算将表达式分成很多段，每一段都是一堆与运算拼起来的，对于每一段，这一段是 $1$ 的条件形如某些数必须是 $1$，某些数必须是 $0$，某些数无限制，所以可以用三进制来存储。然后或的意思就是把这些东西并起来。然后具体将这些限制对应的每个方案上的时候，用个高维前缀和就好了。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#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(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e6 + 5;
const int MAXM = 15 + 3;
int n,m;
char F[MAXN];
char str[MAXN];
int a[MAXN];
// and = 16 or = 17
// const 0 = 18 const 1 = 19
int pw[MAXM];
bool f[43046721+233];
int cnt[MAXM];
int trans[(1<<MAXM)+3];

int main(){
    pw[0] = 1;FOR(i,1,MAXM-1) pw[i] = pw[i-1]*3;
    scanf("%d",&m);scanf("%s",F);
    trans[0] = 0;FOR(i,1,(1<<m)-1) trans[i] = trans[i>>1]*3+(i&1);
    int now = 0;
    while(true){
        scanf("%s",str+1);
        if(str[1] == 'E') break;
        if(str[1] == 'N'){now ^= 1;continue;}
        if(str[1] == 'A' || str[1] == 'O') a[++n] = 16+(str[1]=='O');
        if(str[1] == 'a'){
            int len = strlen(str+1),id = 0;
            FOR(i,2,len) id = id*10+str[i]-'0';
            id = m-id+1;
            a[++n] = (now?-1:1)*id;
            now = 0;
        }
        if(str[1] == '0' || str[1] == '1'){
            a[++n] = 18+((str[1]=='1')^now);
            now = 0;
        }
    }
    int lst = 1;
    std::vector<P> S;
    FOR(i,2,n){
        if(a[i] == 17){
            S.pb(MP(lst,i-1));
            lst = i+1;
        }
    }
    S.pb(MP(lst,n));
    // 0=0
    // 1=1
    // 2=no limit
    for(auto x:S){
        CLR(cnt,-1);
        bool flag = 1;
        FOR(i,x.fi,x.se){
            if(a[i] == 16) continue;
            if(a[i] == 18 || a[i] == 19){flag &= (a[i]==19);continue;}
            int t = std::abs(a[i]),sgn = a[i]>0;
            if(cnt[t] == -1) cnt[t] = sgn;
            else flag &= (!(cnt[t]^sgn));
        }
        if(!flag) continue;
        int zt = 0;
        FOR(i,1,m){
            if(cnt[i] == -1) cnt[i] = 2;
            zt += cnt[i]*pw[i-1];
        }
        f[zt] = 1;
    }
    FOR(i,0,m-1){
        FOR(S,0,pw[m]){
            f[S] |= f[S-((S/pw[i])%3)*pw[i]+2*pw[i]];
        }
    }
    bool flag = 1;
    FOR(S,0,(1<<m)-1) flag &= (f[trans[S]]==F[S]-'0');
    puts(flag?"YES":"NO");
    return 0;
}

C

代价等价于路径最小值乘路径长度。

边分治，预处理出每个点到根的最小值 $mn_i$ 和距离 $d_i$，考虑两个点 $i,j$，如果 $mn_i \leq mn_j$ 贡献就是 $(d_i+d_j)mn_i$，这个相当于是求 $d_j$ 的后缀最大值；如果 $mn_i > mn_j$ 就是 $(d_i+d_j)mn_j$，相当于是个二次函数求最值，搞个凸包就行了。

注意两点：

凸包排序的时候第二维要按照 $y$ 坐标对应排序，不然会锅
边分治的时候不能同时维护点的信息，三度化之后路径上的点信息都被破坏了，我们要把点的信息转到边上，对应到这题就是每个边的边权是相邻两个点的较小值，然后实边距离为 $1$，虚边距离为 $0$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#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(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;

int n,a[MAXN];

struct Edge{
    int to,w1,w2,nxt;
}e[MAXN<<1];
int head[MAXN],cnt = 1;

inline void add(int u,int v,int w1,int w2){
    e[++cnt] = (Edge){v,w1,w2,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,w1,w2,head[v]};head[v] = cnt;
}

std::vector<int> G[MAXN];
int _n;

inline void dfs(int v,int fa=0){
    int las = v;
    for(auto x:G[v]){
        if(x == fa) continue;
        add(las,x,std::min(a[v],a[x]),1);++n;add(las,n,1e9,0);las = n;
    }
    for(auto x:G[v]){
        if(x == fa) continue;
        dfs(x,v);
    }
}

int rt,mx[MAXN];
int sz[MAXN];
bool vis[MAXN];

inline void getroot(int v,int fa=0){
    sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa || vis[i>>1]) continue;
        getroot(e[i].to,v);sz[v] += sz[e[i].to];
        mx[i>>1] = std::max(sz[e[i].to],mx[0]-sz[e[i].to]);
        rt = mx[rt] < mx[i>>1] ? rt : i>>1;
    }
}

struct Node{
    LL x,y;
    Node(LL x=0,LL y=0) : x(x),y(y) {}

    inline Node operator - (const Node &t) const {return Node(x-t.x,y-t.y);}
    inline LL operator * (const Node &t) const {return x*t.y-y*t.x;}
};

LL ans[MAXN];

struct node{
    int dis,mn,id;
    node(int dis=0,int mn=0,int id=0) : dis(dis),mn(mn),id(id) {}

    inline bool operator < (const node &t) const {//  保证凸包正确性
        return mn < t.mn || mn == t.mn && dis > t.dis;
    }
};

std::vector<node> ls,rs;

inline void dfs2(int o,int v,int dep=1,int val=1e9,int fa=0){
    if(v <= _n) (o?rs:ls).pb(node(dep,std::min(val,a[v]),v));
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa || vis[i>>1]) continue;
        dfs2(o,e[i].to,dep+e[i].w2,std::min(val,e[i].w1),v);
    }
}

int suf[MAXN];
std::vector<Node> cov;

inline LL get(const Node &v,int x){
    return -v.x*x+v.y;
}

bool flag = 0;

inline LL query(int x){
    if(cov.empty()) return 0;
    if(cov.size() == 1) return get(cov[0],x);
    int l = 0,r = (int)cov.size()-2;LL ans = get(cov.back(),x);
    while(l <= r){
        int mid = (l + r) >> 1;
        LL ls = get(cov[mid],x),rs = get(cov[mid+1],x);
        if(ls <= rs) ans = std::max(ans,rs),l = mid+1;
        else ans = std::max(ans,ls),r = mid-1;
    }
    return ans;
}

inline void solve(std::vector<node> &L,std::vector<node> &R){// L <- R
    if(L.empty() || R.empty()) return;
    suf[R.size()] = 0;
    ROF(i,(int)R.size()-1,0) suf[i] = std::max(suf[i+1],R[i].dis);
    int ps = 0;
    for(auto x:L){
        while(ps < R.size() && R[ps].mn < x.mn) ++ps;
        ans[x.id] = std::max(ans[x.id],1ll*(suf[ps]+x.dis)*x.mn);
    }
    ps = 0;cov.clear();
    for(auto x:L){
        while(ps < R.size() && R[ps].mn < x.mn){
            Node p = Node(-R[ps].mn,1ll*R[ps].mn*R[ps].dis);
            while(cov.size() >= 2 && (cov.back()-cov[(int)cov.size()-2])*(p-cov.back()) <= 0) cov.pop_back();
            cov.pb(p);
            ++ps;
        }
        ans[x.id] = std::max(ans[x.id],query(x.dis));
    }
    cov.clear();
}

inline void work(int edge){
    if(!edge) return;
    int u = e[edge<<1].to,v = e[edge<<1|1].to;
    vis[edge] = 1;dfs2(0,u,1,e[edge<<1].w1);dfs2(1,v,e[edge<<1].w2,e[edge<<1].w1);
    std::sort(all(ls));std::sort(all(rs));
    solve(ls,rs);solve(rs,ls);
    ls.clear();rs.clear();
    mx[rt = 0] = sz[u];getroot(u);work(rt);
    mx[rt = 0] = sz[v];getroot(v);work(rt);
}

int main(){
    scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),ans[i] = a[i];_n = n;
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    dfs(1);
    mx[rt = 0] = n;getroot(1);
    work(rt);
    FOR(i,1,_n) printf("%lld%c",ans[i]," \n"[i==_n]);
    return 0;
}

Last modification：July 11th, 2022 at 06:10 pm

如果觉得我的文章对你有用，请随意赞赏

20zr联赛集训day17

RainAir • 2020 年 11 月 03 日

B 被降智了，所以掉分了。

A

考虑将这个串拆成三部分考虑：114，5，14。

$$ \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times (j-i-1-(s_{j-1,a_i}-s_{i,a_i})-(s_{j-1,a_j}-s_{i,a_j})) $$

我们考虑将这个式子拆成可以分开维护的形式：

$$ \begin{aligned} \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(j-1-s_{j-1,a_i}-s_{j-1,a_j})\\ +\sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(-i+s_{i,a_i}+s_{i,a_j})\\ \end{aligned} $$

我们枚举 $i$ 和 $a_j$，维护对应的 $\sum g_{j,a_i}\times (j-1-s_{j-1,a_i}-s_{j-1,a_j})$ 和 $\sum g_{j,a_i}$ 即可。

可以用一些滚动数组技巧做到空间 $O((\Sigma) ^2)$。放个卡完空间的代码：

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#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(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;
const int ha = 114514;
char str[MAXN];
int n;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int sm1[26][26],sm2[26][26];
int smf[26],smg[26];

int main(){
    scanf("%s",str+1);n = strlen(str+1);
    auto f = [&](int i,int j){
        return str[i]-'a' == j ? 0 : (1ll*smf[j]*(smf[j]-1)/2)%ha;
    };
    auto g = [&](int i,int j){
        return str[i]-'a' == j ? 0 : smg[j];
    };
    int ans = 0;
    FOR(i,1,n-1) add(smf[str[i]-'a'],1);
    ROF(i,n,1){
        FOR(j,0,25){
            if(str[i]-'a' == j) continue;
            add(ans,1ll*f(i,j)*sm2[j][str[i]-'a']%ha);
            int coe = (smf[j]+smf[str[i]-'a']+1-i+ha)%ha;
            coe = 1ll*coe*f(i,j)%ha;
            add(ans,1ll*coe*sm1[j][str[i]-'a']%ha);
        }
        FOR(j,0,25){
            add(sm1[str[i]-'a'][j],g(i,j));
            int coe = (i-1-smf[j]-smf[str[i]-'a']+ha+ha)%ha;
            add(sm2[str[i]-'a'][j],1ll*g(i,j)*coe%ha);
        }
        if(i-1) add(smf[str[i-1]-'a'],ha-1);
        add(smg[str[i]-'a'],1);
    }
    printf("%d\n",ans);
    return 0;
}

B

这个题没有括号！！表达式求值没有括号要考虑按照某个运算分成若干块处理。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#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(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e6 + 5;
const int MAXM = 15 + 3;
int n,m;
char F[MAXN];
char str[MAXN];
int a[MAXN];
// and = 16 or = 17
// const 0 = 18 const 1 = 19
int pw[MAXM];
bool f[43046721+233];
int cnt[MAXM];
int trans[(1<<MAXM)+3];

int main(){
    pw[0] = 1;FOR(i,1,MAXM-1) pw[i] = pw[i-1]*3;
    scanf("%d",&m);scanf("%s",F);
    trans[0] = 0;FOR(i,1,(1<<m)-1) trans[i] = trans[i>>1]*3+(i&1);
    int now = 0;
    while(true){
        scanf("%s",str+1);
        if(str[1] == 'E') break;
        if(str[1] == 'N'){now ^= 1;continue;}
        if(str[1] == 'A' || str[1] == 'O') a[++n] = 16+(str[1]=='O');
        if(str[1] == 'a'){
            int len = strlen(str+1),id = 0;
            FOR(i,2,len) id = id*10+str[i]-'0';
            id = m-id+1;
            a[++n] = (now?-1:1)*id;
            now = 0;
        }
        if(str[1] == '0' || str[1] == '1'){
            a[++n] = 18+((str[1]=='1')^now);
            now = 0;
        }
    }
    int lst = 1;
    std::vector<P> S;
    FOR(i,2,n){
        if(a[i] == 17){
            S.pb(MP(lst,i-1));
            lst = i+1;
        }
    }
    S.pb(MP(lst,n));
    // 0=0
    // 1=1
    // 2=no limit
    for(auto x:S){
        CLR(cnt,-1);
        bool flag = 1;
        FOR(i,x.fi,x.se){
            if(a[i] == 16) continue;
            if(a[i] == 18 || a[i] == 19){flag &= (a[i]==19);continue;}
            int t = std::abs(a[i]),sgn = a[i]>0;
            if(cnt[t] == -1) cnt[t] = sgn;
            else flag &= (!(cnt[t]^sgn));
        }
        if(!flag) continue;
        int zt = 0;
        FOR(i,1,m){
            if(cnt[i] == -1) cnt[i] = 2;
            zt += cnt[i]*pw[i-1];
        }
        f[zt] = 1;
    }
    FOR(i,0,m-1){
        FOR(S,0,pw[m]){
            f[S] |= f[S-((S/pw[i])%3)*pw[i]+2*pw[i]];
        }
    }
    bool flag = 1;
    FOR(S,0,(1<<m)-1) flag &= (f[trans[S]]==F[S]-'0');
    puts(flag?"YES":"NO");
    return 0;
}

C

代价等价于路径最小值乘路径长度。

注意两点：

凸包排序的时候第二维要按照 $y$ 坐标对应排序，不然会锅
边分治的时候不能同时维护点的信息，三度化之后路径上的点信息都被破坏了，我们要把点的信息转到边上，对应到这题就是每个边的边权是相邻两个点的较小值，然后实边距离为 $1$，虚边距离为 $0$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#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(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;

int n,a[MAXN];

struct Edge{
    int to,w1,w2,nxt;
}e[MAXN<<1];
int head[MAXN],cnt = 1;

inline void add(int u,int v,int w1,int w2){
    e[++cnt] = (Edge){v,w1,w2,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,w1,w2,head[v]};head[v] = cnt;
}

std::vector<int> G[MAXN];
int _n;

inline void dfs(int v,int fa=0){
    int las = v;
    for(auto x:G[v]){
        if(x == fa) continue;
        add(las,x,std::min(a[v],a[x]),1);++n;add(las,n,1e9,0);las = n;
    }
    for(auto x:G[v]){
        if(x == fa) continue;
        dfs(x,v);
    }
}

int rt,mx[MAXN];
int sz[MAXN];
bool vis[MAXN];

inline void getroot(int v,int fa=0){
    sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa || vis[i>>1]) continue;
        getroot(e[i].to,v);sz[v] += sz[e[i].to];
        mx[i>>1] = std::max(sz[e[i].to],mx[0]-sz[e[i].to]);
        rt = mx[rt] < mx[i>>1] ? rt : i>>1;
    }
}

struct Node{
    LL x,y;
    Node(LL x=0,LL y=0) : x(x),y(y) {}

    inline Node operator - (const Node &t) const {return Node(x-t.x,y-t.y);}
    inline LL operator * (const Node &t) const {return x*t.y-y*t.x;}
};

LL ans[MAXN];

struct node{
    int dis,mn,id;
    node(int dis=0,int mn=0,int id=0) : dis(dis),mn(mn),id(id) {}

    inline bool operator < (const node &t) const {//  保证凸包正确性
        return mn < t.mn || mn == t.mn && dis > t.dis;
    }
};

std::vector<node> ls,rs;

inline void dfs2(int o,int v,int dep=1,int val=1e9,int fa=0){
    if(v <= _n) (o?rs:ls).pb(node(dep,std::min(val,a[v]),v));
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa || vis[i>>1]) continue;
        dfs2(o,e[i].to,dep+e[i].w2,std::min(val,e[i].w1),v);
    }
}

int suf[MAXN];
std::vector<Node> cov;

inline LL get(const Node &v,int x){
    return -v.x*x+v.y;
}

bool flag = 0;

inline LL query(int x){
    if(cov.empty()) return 0;
    if(cov.size() == 1) return get(cov[0],x);
    int l = 0,r = (int)cov.size()-2;LL ans = get(cov.back(),x);
    while(l <= r){
        int mid = (l + r) >> 1;
        LL ls = get(cov[mid],x),rs = get(cov[mid+1],x);
        if(ls <= rs) ans = std::max(ans,rs),l = mid+1;
        else ans = std::max(ans,ls),r = mid-1;
    }
    return ans;
}

inline void solve(std::vector<node> &L,std::vector<node> &R){// L <- R
    if(L.empty() || R.empty()) return;
    suf[R.size()] = 0;
    ROF(i,(int)R.size()-1,0) suf[i] = std::max(suf[i+1],R[i].dis);
    int ps = 0;
    for(auto x:L){
        while(ps < R.size() && R[ps].mn < x.mn) ++ps;
        ans[x.id] = std::max(ans[x.id],1ll*(suf[ps]+x.dis)*x.mn);
    }
    ps = 0;cov.clear();
    for(auto x:L){
        while(ps < R.size() && R[ps].mn < x.mn){
            Node p = Node(-R[ps].mn,1ll*R[ps].mn*R[ps].dis);
            while(cov.size() >= 2 && (cov.back()-cov[(int)cov.size()-2])*(p-cov.back()) <= 0) cov.pop_back();
            cov.pb(p);
            ++ps;
        }
        ans[x.id] = std::max(ans[x.id],query(x.dis));
    }
    cov.clear();
}

inline void work(int edge){
    if(!edge) return;
    int u = e[edge<<1].to,v = e[edge<<1|1].to;
    vis[edge] = 1;dfs2(0,u,1,e[edge<<1].w1);dfs2(1,v,e[edge<<1].w2,e[edge<<1].w1);
    std::sort(all(ls));std::sort(all(rs));
    solve(ls,rs);solve(rs,ls);
    ls.clear();rs.clear();
    mx[rt = 0] = sz[u];getroot(u);work(rt);
    mx[rt = 0] = sz[v];getroot(v);work(rt);
}

int main(){
    scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),ans[i] = a[i];_n = n;
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    dfs(1);
    mx[rt = 0] = n;getroot(1);
    work(rt);
    FOR(i,1,_n) printf("%lld%c",ans[i]," \n"[i==_n]);
    return 0;
}

20zr联赛集训day17

A

B

C

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

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

CSP2019 游记

AGC018 E

utpc2012 Wrapping 题解

点分治初探

CF1450 题解

网络流建模总结

20zr联赛集训day17

A

B

C