列表

详情

NC252837. Forever Young

描述

I remember what someone said to me a long time ago, "The path you choose, even if you walk on your knees, you have to finish it". Friends, although the world is getting more and more impetuous, as long as we can persist in our efforts for the sake of our once pure dreams and moving motives, we can remain true to ourselves all the way, no matter what others do.

As a retired contestant, Colin hopes that all participants will always have a young heart and an eternal love for algorithms and competitive programming.

Given a tree T consisting of n vertices (indexed from 1 to n). Vertex 1 is the root.

We define that vertex u is an ancestor of vertex v if and only if u is on the path from v to the root.

Then we define subtree_u as the set of all vertices v satisfies that u is an ancestor of v .

Now Colin and Eva give each node u two integer weights c_u,e_u , then we define :

ans_u=\sum_{x\in subtree_u}\sum_{y\in subtree_u} \min\{|c_x-c_y|,|e_x-e_y|\} \mod 10^9+7

Please calculate ans_u for each vertex u\in [1, n] .

输入描述

The first line contains a single integer n\text{ } (1 \le n \le 5 \times 10^5) , representing the number of vertices.

For the following n - 1 lines, each line contains two integers u_i, v_i \text{ } (1 \le u_i , v_i \le n, u_i \neq v_i) , representing that there is an edge connecting vertex u_i and vertex v_i . It's guaranteed that the given edges form a tree.

For the following n lines, the i-th line contains two integers c_i,e_i \text{ } (1 \le c_i, e_i\le 10^9) , representing the two weights of vertex i.

输出描述

Output n lines.

For i-th line output a single integer ans_i .

示例1

输入: 

5
1 2
1 3
2 4
2 5
9 5
2 8
7 1
4 3
6 6

输出: 

44
12
0
0
0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 5620ms, 内存消耗: 367456K, 提交时间: 2023-06-12 17:43:59 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 500010;
const int M = 1000010;
const int mod = 1e9+7;
int n, m;
int head[N], pre[M], ver[M], tot;
void add(int x,int y){
    ver[++tot]=y; pre[tot]=head[x]; head[x]=tot;
}
ll w[4][N];
struct seg{
    int idx, rt[N];
    int ls[N*20], rs[N*20];
    ll sum[N*20], val[N*20], ans[N*20];
    void pushup(int p){
        ans[p]=(ans[ls[p]]+ans[rs[p]]+sum[rs[p]]*val[ls[p]]%mod-sum[ls[p]]*val[rs[p]]%mod+mod)%mod;
    }
    int newcode(){
        int x=++idx;
        sum[x]=val[x]=ans[x]=ls[x]=rs[x]=0;
        return x;
    }
    void update(int &p,int x,int l,int r,int d){
        if (!p) p=newcode();
        sum[p]+=d; val[p]++;
        if (l==r) return;
        int mid=(l+r)>>1;
        if (x<=mid) update(ls[p],x,l,mid,d);
        else update(rs[p],x,mid+1,r,d);
        pushup(p);
    }
    int merge(int p,int q,int l,int r){
        if (!p || !q) return p|q;
        val[p]+=val[q]; sum[p]=(sum[p]+sum[q])%mod;
        if (l==r) return p;
        int mid=(l+r)>>1;
        ls[p]=merge(ls[p],ls[q],l,mid);
        rs[p]=merge(rs[p],rs[q],mid+1,r);
        pushup(p);
        return p;
    }
}T;
int id[4][N], len[4];
ll ans[N][4];
void dfs(int x,int f,int o){
    T.update(T.rt[x],w[o][x],1,len[o],id[o][w[o][x]]);
//    printf("x=%d\n",x);
    for (int i=head[x]; i; i=pre[i]){
        int v=ver[i];
        if (v==f) continue;
        dfs(v,x,o);
        T.rt[x]=T.merge(T.rt[x],T.rt[v],1,len[o]);
    }
    ans[x][o]=T.ans[T.rt[x]];
}
int main(){
    cin>>n;
    for (int i=1;i<n;++i){
        int x,y; cin>>x>>y;
        add(x,y); add(y,x);
    }
    for (int i=1;i<=n;++i) {
        cin>>w[0][i]>>w[1][i];
        w[2][i]=(w[0][i]+w[1][i]);
        w[3][i]=(w[0][i]-w[1][i]);
        for (int o=0;o<4;++o) id[o][i]=w[o][i];
    }
    for (int o=0;o<4;++o){
        sort(id[o]+1,id[o]+1+n); len[o]=unique(id[o]+1,id[o]+1+n)-id[o]-1;
//        for (int i=1;i<=n;++i) printf("o=%d i=%d w=%d\n",o,i,w[o][i]);
        for (int i=1;i<=n;++i) w[o][i]=lower_bound(id[o]+1,id[o]+1+len[o],w[o][i])-id[o];
//        for (int i=1;i<=n;++i) printf("o=%d i=%d w=%d\n",o,i,w[o][i]);
    }
    for (int o=0;o<4;++o){
        for (int i=1;i<=len[o];++i) id[o][i]=(id[o][i]%mod+mod)%mod;
    }
    for (int o=0;o<4;++o) {
        dfs(1,0,o);
        for (int i=1;i<=n;++i) T.rt[i]=0; T.idx=0;
    }
    for (int i=1;i<=n;++i){
        ll res=(ans[i][0]*2+ans[i][1]*2-ans[i][2]-ans[i][3]+mod*2)%mod;
//        for (int j=0;j<4;++j) printf("i=%d j=%d ans=%d\n",i,j,ans[i][j]);
//        printf("i=%d res=%lld\n",i,res);
        
        printf("%lld\n",res);
    }
    
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 5808ms, 内存消耗: 368340K, 提交时间: 2023-06-04 13:41:45 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 500010;
const int M = 1000010;
const int mod = 1e9+7;
int n, m;
int head[N], pre[M], ver[M], tot;
void add(int x,int y){
    ver[++tot]=y; pre[tot]=head[x]; head[x]=tot;
}
ll w[4][N];
struct seg{
    int idx, rt[N];
    int ls[N*20], rs[N*20];
    ll sum[N*20], val[N*20], ans[N*20];
    void pushup(int p){
        ans[p]=(ans[ls[p]]+ans[rs[p]]+sum[rs[p]]*val[ls[p]]%mod-sum[ls[p]]*val[rs[p]]%mod+mod)%mod;
    }
    int newcode(){
        int x=++idx;
        sum[x]=val[x]=ans[x]=ls[x]=rs[x]=0;
        return x;
    }
    void update(int &p,int x,int l,int r,int d){
        if (!p) p=newcode();
        sum[p]+=d; val[p]++;
        if (l==r) return;
        int mid=(l+r)>>1;
        if (x<=mid) update(ls[p],x,l,mid,d);
        else update(rs[p],x,mid+1,r,d);
        pushup(p);
    }
    int merge(int p,int q,int l,int r){
        if (!p || !q) return p|q;
        val[p]+=val[q]; sum[p]=(sum[p]+sum[q])%mod;
        if (l==r) return p;
        int mid=(l+r)>>1;
        ls[p]=merge(ls[p],ls[q],l,mid);
        rs[p]=merge(rs[p],rs[q],mid+1,r);
        pushup(p);
        return p;
    }
}T;
int id[4][N], len[4];
ll ans[N][4];
void dfs(int x,int f,int o){
    T.update(T.rt[x],w[o][x],1,len[o],id[o][w[o][x]]);
//    printf("x=%d\n",x);
    for (int i=head[x]; i; i=pre[i]){
        int v=ver[i];
        if (v==f) continue;
        dfs(v,x,o);
        T.rt[x]=T.merge(T.rt[x],T.rt[v],1,len[o]);
    }
    ans[x][o]=T.ans[T.rt[x]];
}
int main(){
    cin>>n;
    for (int i=1;i<n;++i){
        int x,y; cin>>x>>y;
        add(x,y); add(y,x);
    }
    for (int i=1;i<=n;++i) {
        cin>>w[0][i]>>w[1][i];
        w[2][i]=(w[0][i]+w[1][i]);
        w[3][i]=(w[0][i]-w[1][i]);
        for (int o=0;o<4;++o) id[o][i]=w[o][i];
    }
    for (int o=0;o<4;++o){
        sort(id[o]+1,id[o]+1+n); len[o]=unique(id[o]+1,id[o]+1+n)-id[o]-1;
//        for (int i=1;i<=n;++i) printf("o=%d i=%d w=%d\n",o,i,w[o][i]);
        for (int i=1;i<=n;++i) w[o][i]=lower_bound(id[o]+1,id[o]+1+len[o],w[o][i])-id[o];
//        for (int i=1;i<=n;++i) printf("o=%d i=%d w=%d\n",o,i,w[o][i]);
    }
    for (int o=0;o<4;++o){
        for (int i=1;i<=len[o];++i) id[o][i]=(id[o][i]%mod+mod)%mod;
    }
    for (int o=0;o<4;++o) {
        dfs(1,0,o);
        for (int i=1;i<=n;++i) T.rt[i]=0; T.idx=0;
    }
    for (int i=1;i<=n;++i){
        ll res=(ans[i][0]*2+ans[i][1]*2-ans[i][2]-ans[i][3]+mod*2)%mod;
//        for (int j=0;j<4;++j) printf("i=%d j=%d ans=%d\n",i,j,ans[i][j]);
//        printf("i=%d res=%lld\n",i,res);
        printf("%lld\n",res);
    }
    return 0;
}

上一题

© 2025 nowcoder.com