제출 #1291272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291272		simona1230	Designated Cities (JOI19_designated_cities)	C++20	7 / 100	205 ms	54596 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;
const long long maxn=2*1e5+5;

long long n;
vector<long long> v[maxn],a[maxn],b[maxn];
long long q;
long long e[maxn];
long long sum;

void read()
{
    cin>>n;
    for(long long i=1;i<n;i++)
    {
        long long v1,v2,d1,d2;
        cin>>v1>>v2>>d1>>d2;
        v[v1].push_back(v2);
        v[v2].push_back(v1);
        a[v1].push_back(d1);
        b[v1].push_back(d2);
        a[v2].push_back(d2);
        b[v2].push_back(d1);
        sum+=d1;
        sum+=d2;
    }

    cin>>q;
    for(long long i=1;i<=q;i++)
        cin>>e[i];
}

long long up[maxn],dw[maxn];
long long vl[maxn];
long long maxx[maxn];

void dfs(long long i,long long p)
{
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;

        dfs(nb,i);
        up[i]+=up[nb]+b[i][j];
        dw[i]+=dw[nb]+a[i][j];

        maxx[i]=max(maxx[i],maxx[nb]+a[i][j]);
    }
}
long long ans,ans2;

void dfs1(long long i,long long p)
{
    int v1=-1,v2=-1;
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;
        vl[nb]=vl[i]-b[i][j]+a[i][j];
        ans=max(ans,vl[nb]);
        dfs1(nb,i);

        if(v1==-1||v1<=maxx[nb]+a[i][j])
        {
            v2=v1;
            v1=maxx[nb]+a[i][j];
        }
        else if(v2==-1||v2<=maxx[nb]+a[i][j])
        {
            v2=maxx[nb]+a[i][j];
        }
    }

    if(v1!=-1&&v2!=-1)
    {
        ans2=max(ans2,vl[i]+v1+v2);
    }
}

void solve1()
{
    if(n==2)
    {
        if(e[1]==1)
            cout<<min(a[1][0],b[1][0])<<endl;
        else cout<<0<<endl;
        return;
    }

    int s=1;
    for(int i=1;i<=n;i++)
        if(v[i].size()>=2)s=i;
    dfs(s,0);
    ans=vl[s]=up[s];
    dfs1(s,0);
    if(e[1]==2)ans=ans2;
    cout<<sum-ans<<endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve1();
	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44