Submission #1291277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291277		simona1230	Designated Cities (JOI19_designated_cities)	C++20	16 / 100	2098 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)
{
    long long 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);
    }
}

long long s;

void solve1()
{
    if(n==2)
    {
        for(long long i=1;i<=q;i++)
        if(e[i]==1)
            cout<<min(a[1][0],b[1][0])<<endl;
        else cout<<0<<endl;
        exit(0);
    }
    for(long long i=1;i<=n;i++)
        if(v[i].size()>=2)s=i;
    dfs(s,0);
    ans=vl[s]=up[s];
    dfs1(s,0);

    if(q==1&&e[1]==1||q==1&&e[1]==2)
    {
        if(e[1]==2)ans=ans2;
        cout<<sum-ans<<endl;
        exit(0);
    }
}

vector<long long> l;
bool on[maxn];
long long in[maxn];
long long curr,qr;

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

        dfsc(nb,i);

        if(in[nb]!=0)
        {
            curr+=a[i][j];
        }

        if(in[nb]!=qr)
        {
            curr+=b[i][j];
        }

        in[i]+=in[nb];
    }
}

long long ansp;

void rec(long long i)
{
    if(i==l.size())
    {
        curr=0;
        dfsc(s,0);
        if(in[s]==qr)
        {
            /*cout<<curr<<": ";
            for(long long j=1;j<=n;j++)
                cout<<in[j]<<" ";
            cout<<endl;*/
            ansp=max(ansp,curr);
        }
        return;
    }

    on[l[i]]=1;
    rec(i+1);
    on[l[i]]=0;
    rec(i+1);
}

void brute()
{
    solve1();
    for(long long i=1;i<=n;i++)
    {
        if(v[i].size()>=2)s=i;
        if(v[i].size()==1)
            l.push_back(i);
    }

    for(long long i=1;i<=q;i++)
    {
        qr=e[i];
        if(qr==1)
        {
            cout<<sum-ans<<endl;
            continue;
        }
        ansp=0;
        rec(0);
        cout<<sum-ansp<<endl;
    }
}

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

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