제출 #125099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125099		davitmarg	Chase (CEOI17_chase)	C++17	0 / 100	524 ms	17184 KiB

chase

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,k,color[100005],used[100005],cnt[100005],c;
LL a[100005],ans;
vector<int> g[100005];

void dfsCnt(int v,int p=0)
{
	cnt[v]=1;
    for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		if(used[to] || to==p)
			continue;
		dfsCnt(to,v);
		cnt[v]+=cnt[to];
	}
}

int centroid(int v)
{
	dfsCnt(v);
    c++;
    queue<int> q;
    q.push(v);
    while(!q.empty())
	{
        int u=q.front();
        q.pop();
        color[u]=c;
        bool can=((cnt[v]-cnt[u])*2<=cnt[v]);
        for(int i=0;i<g[u].size();i++)
		{
			int to=g[u][i];
            if(color[to]==c || used[to])
				continue;
            q.push(to);
            if(cnt[to]*2>cnt[v])
                can=0;
		}
        if(can)
		{
			used[u]=1;
			return u;
		}
	}
}


LL d[4*100005],t[4*100005];

void push(int v,int l,int r,bool f=1)
{
    if(d[v]==-1)
		return;
    if(l!=r)
	{
		d[v*2]=d[v];
		d[v*2+1]=d[v];
        if(f)
		{
			int m=(l+r)/2;
            push(v*2,l,m,0);
            push(v*2+1,m+1,r,0);
		}
	}
    t[v]=d[v];
    d[v]=-1;
}

void build(int v,int l,int r)
{
    d[v]=-1;
    t[v]=-mod*mod;
    if(l==r)
		return;
    int m=(l+r)/2;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
}

void update(int v,int l,int r,int pos,LL val)
{
	push(v,l,r);
	if(l==r)
	{
        t[v]=max(t[v],val);
        return;
	}
    int m=(l+r)/2;
    if(pos<=m)
        update(v*2,l,m,pos,val);
	else
        update(v*2+1,m+1,r,pos,val);
	t[v]=max(t[v*2],t[v*2+1]);
}

LL get(int v,int l,int r,int i,int j)
{
    if(i>j)
		return -mod *mod;
	push(v,l,r);
	if(l==i && r==j)
        return t[v];
    int m=(l+r)/2;
    return max(
		get(v*2,l,m,i,min(m,j)),
		get(v*2+1,m+1,r,max(m+1,i),j));
}

vector<pair<LL,int>> upd;
LL start;

void dfs(int v,int p,int depth,LL sum)
{
    if(depth>k)
		return;
	for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
        if(to==p)
            continue;
		sum+=a[to];
	}
	LL x=get(1,0,k,0,k-depth+1);
    ans=max(ans,x+sum-a[v]-start);
	upd.PB(MP(sum,depth));

	for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
        if(used[to] || to==p)
            continue;
        dfs(to,v,depth+1,sum);
	}
}

void solve(int v)
{
    vector<int> nxt;
    start=a[v];
    for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
		start+=a[to];
	}

    d[1]=-mod*mod;
    update(1,0,k,0,0);
    update(1,0,k,1,start);
    for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
        if(used[to])
			continue;
        upd.clear();
		dfs(to,v,2,start);
		for(int i=0;i<upd.size();i++)
			update(1,0,k,upd[i].second,upd[i].first);
	}
	ans=max(ans,get(1,0,k,0,k)-a[v]);
	reverse(all(g[v]));

    d[1]=-mod*mod;
    update(1,0,k,0,0);
    update(1,0,k,1,start);
    for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
        if(used[to])
			continue;
        upd.clear();
		dfs(to,v,2,start);
		for(int i=0;i<upd.size();i++)
			update(1,0,k,upd[i].second,upd[i].first);
	}

    for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
        if(used[to])
			continue;
        solve(centroid(to));
	}
}

int main()
{
    cin>>n>>k;
    build(1,0,n);
    for(int i=1;i<=n;i++)
		scanf("%lld",a+i);
    for(int i=1;i<=n-1;i++)
    {
		int a,b;
		scanf("%d%d",&a,&b);
		g[a].PB(b);
		g[b].PB(a);
    }
    solve(centroid(1));
    cout<<ans<<endl;
	return 0;
}


/*


5 3
1 2 3 4 5
1 2
1 3
3 4
3 5

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12


*/

컴파일 시 표준 에러 (stderr) 메시지

chase.cpp: In function 'void dfsCnt(int, int)':
chase.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
chase.cpp: In function 'int centroid(int)':
chase.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[u].size();i++)
                     ~^~~~~~~~~~~~
chase.cpp: In function 'void dfs(int, int, int, long long int)':
chase.cpp:140:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
chase.cpp:151:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
chase.cpp: In function 'void solve(int)':
chase.cpp:164:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
chase.cpp:173:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
chase.cpp:180:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<upd.size();i++)
               ~^~~~~~~~~~~
chase.cpp:189:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
chase.cpp:196:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<upd.size();i++)
               ~^~~~~~~~~~~
chase.cpp:200:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
chase.cpp: In function 'int centroid(int)':
chase.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
chase.cpp: In function 'int main()':
chase.cpp:214:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",a+i);
   ~~~~~^~~~~~~~~~~~
chase.cpp:218:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30