/ tabris /

记录详情

Accepted

/in/foo.cc: In function 'void Dfs(long long int, long long int)':
/in/foo.cc:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<mp[u].size();i++)
                ~^~~~~~~~~~~~~
# 状态 耗时 内存占用
#1 Accepted 10ms 18.316 MiB
#2 Accepted 11ms 18.059 MiB
#3 Accepted 8ms 19.809 MiB
#4 Accepted 24ms 19.305 MiB
#5 Accepted 36ms 22.059 MiB
#6 Accepted 35ms 22.059 MiB
#7 Accepted 7ms 18.105 MiB
#8 Accepted 22ms 21.824 MiB
#9 Accepted 597ms 54.309 MiB
#10 Accepted 618ms 56.18 MiB

代码

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long int
vector<ll>mp[505000];
ll a[505000];
ll L[505000];
ll R[505000];
ll cnt;
void Dfs(ll u,ll from)
{
    L[u]=++cnt;
    for(ll i=0;i<mp[u].size();i++)
    {
        ll v=mp[u][i];
        if(v==from)continue;
        Dfs(v,u);
    }
    R[u]=cnt;
}
/******************************************/
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
ll tree[505000*4];
void pushup(ll rt)
{
    tree[rt]=tree[rt*2]+tree[rt*2+1];
}
void build(ll l,ll r,ll rt)
{
    if(l==r)
    {
        tree[rt]=0;
        return ;
    }
    ll m=(l+r)/2;
    build(lson);build(rson);pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(l>=L&&r<=R)
    {
        return tree[rt];
    }
    ll ans=0;
    ll m=(l+r)/2;
    if(L<=m)ans+=query(L,R,lson);
    if(R>m)ans+=query(L,R,rson);
    pushup(rt);
    return ans;
}
void update(ll p,ll c,ll l,ll r,ll rt)
{
    if(l==r)
    {
        tree[rt]+=c;
        return ;
    }
    ll m=(l+r)/2;
    if(p<=m)update(p,c,lson);
    if(p>m)update(p,c,rson);
    pushup(rt);
    return ;
}
/******************************************/
int main()
{
    ll n;
    while(~scanf("%lld",&n))
    {
        cnt=0;
        ll sum=0;
        for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),mp[i].clear(),sum+=a[i];
        for(ll i=1;i<=n-1;i++)
        {
            ll x,y;scanf("%lld%lld",&x,&y);
            mp[x].push_back(y);
            mp[y].push_back(x);
        }
        ll ans1=0,ans2=sum;
        ll maxn=100000000000000000ll;
        Dfs(1,-1);
        build(1,n,1);
        for(ll i=1;i<=n;i++)update(L[i],a[i],1,n,1);
        for(ll i=1;i<=n;i++)
        {
            ll A=query(L[i],R[i],1,n,1);
            ll B=sum-A;
            if(A>B)swap(A,B);
            if(abs(A-B)<maxn)
            {
                maxn=abs(A-B);
                ans1=A;ans2=B;
            }
        }
        printf("%lld %lld\n",ans1,ans2);
    }
}

信息

递交者
类型
递交
语言
C++
递交时间
2017-09-18 19:45:52
评测时间
2017-09-18 19:45:52
评测机
分数
640
总耗时
1375ms
峰值内存
56.18 MiB