QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#170504#7103. Red Black Treexianggui#WA 1944ms57104kbC++205.9kb2023-09-09 15:24:002023-09-09 15:24:02

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 15:24:02]
  • 评测
  • 测评结果:WA
  • 用时:1944ms
  • 内存:57104kb
  • [2023-09-09 15:24:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
int n,m,q,k;
int dfn[100010],timee;
int key[100010];
int a[100010<<2],tot,root;
bool red[100010],kk[100010];
vector<pair<int, ll> > ed[100010],eed[100010];
int fa[100010][21],deep[100010];
ll sum[100010][21];
ll cost[100010];

void dfs(int x,int f)
{
    dfn[x]=++timee;
    for(int i=1;i<=20;i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        sum[x][i]=sum[fa[x][i-1]][i-1]+sum[x][i-1];
    }
    for(auto i:ed[x])
    {
        int v=i.first;
        ll val=i.second;
        if(v==f) continue;
        deep[v]=deep[x]+1;
        fa[v][0]=x;
        sum[v][0]=val;
        dfs(v, x);
    }
}

void dfs1(int x,int f,ll ss)
{
    if(red[x]) ss=0;
    cost[x]=ss;
    for(auto i:ed[x])
    {
        int v=i.first;
        ll val=i.second;
        if(v==f) continue;
        dfs1(v, x, ss+val);
    }
}

int lca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
    {
        int xx=fa[x][i];
        if(deep[xx]>=deep[y])
        {
            x=xx;
        }
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--)
    {
        int xx=fa[x][i];
        int yy=fa[y][i];
        if(xx!=yy)
        {
            x=xx;
            y=yy;
        }
    }
    return fa[x][0];
}

ll getsum(int x,int y)
{
    ll res=0;
    for(int i=20;i>=0;i--)
    {
        int xx=fa[x][i];
        if(deep[xx]>=deep[y])
        {
            res+=sum[x][i];
            x=xx;
        }
    }
    return res;
}

bool cmp(int x,int y)
{
    return dfn[x]<dfn[y];
}

int id;
ll ans;
ll high[100010];
int fff[100010];
bool maxvis[100010];
int sikey[100010];
void DFS(int x)
{
    if(x==id) maxvis[x]=1;
    if(kk[x]) sikey[x]++;
    for(auto i:eed[x])
    {
        int v=i.first;
        ll val=i.second;
        fff[v]=x;
        DFS(v);
        sikey[x]+=sikey[v];
        maxvis[x]|=maxvis[v];
        high[x]=max(high[x], high[v]+val);
    }
}

int lefkey[100010],silef;
void DFS1(int x)
{
    for(auto i:eed[x])
    {
        int v=i.first;
        ll val=i.second;
        if(maxvis[v])
        {
            DFS1(v);
            if(kk[v]) lefkey[++silef]=v;
            break;
        }
    }
    for(auto i:eed[x])
    {
        int v=i.first;
        ll val=i.second;
        if(maxvis[v]) continue;
        DFS1(v);
        if(kk[v]) lefkey[++silef]=v;
    }
}

ll backmaxx[100010];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>q;
        timee=0;
        for(int i=1;i<=n;i++)
        {
            red[i]=0;
            ed[i].clear();
            dfn[i]=0;
        }
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            red[x]=1;
        }
        for(int i=1;i<n;i++)
        {
            int x,y;
            ll z;
            cin>>x>>y>>z;
            ed[x].push_back(make_pair(y, z));
            ed[y].push_back(make_pair(x, z));
        }
        deep[1]=1;
        dfs(1,0);
        dfs1(1, 0, 0);
        while(q--)
        {
            cin>>k;
            // cout<<"cost:\n";
            for(int i=1;i<=k;i++)
            {
                cin>>key[i];
                kk[key[i]]=1;
                // cout<<cost[key[i]]<<" ";
            }
            // puts("");
            tot=0;
            sort(key+1,key+k+1,cmp);
            for(int i=1;i<k;i++)
            {
                int tem=lca(key[i],key[i+1]);
                a[++tot]=key[i];
                a[++tot]=tem;
            }
            a[++tot]=key[k];
            
            sort(a+1,a+1+tot,cmp);
            tot=unique(a+1,a+1+tot)-(a+1);
            // cout<<"vt:\n";
            for(int i=1;i<=tot;i++)
            {
                // cout<<a[i]<<" ";
                eed[a[i]].clear();
                fff[a[i]]=0;
                maxvis[a[i]]=0;
                high[a[i]]=0;
                sikey[a[i]]=0;
            }
            // puts("");
            // puts("");
            root=a[1];
            // cout<<"bt:\n";
            for(int i=1;i<tot;i++)
            {
                int tem=lca(a[i],a[i+1]);
                ll val=getsum(a[i+1], tem);
                // cout<<tem<<" "<<a[i+1]<<endl;
                eed[tem].push_back(make_pair(a[i+1], val));
            }
            id=0;
            ans=0;
            // cout<<"!\n";
            for(int i=1;i<=k;i++)
            {
                // cout<<key[i]<<" "<<cost[key[i]]<<endl;
                if(cost[key[i]]>ans)
                {
                    ans=cost[key[i]];
                    id=key[i];
                }
            }
            // cout<<id<<endl;
            // cout<<ans<<endl;
            silef=0;
            DFS(root);
            DFS1(root);
            backmaxx[silef+1]=0;
            // for(int i=1;i<=silef;i++)
            // {
            //     cout<<lefkey[i]<<" ";
            // }
            // puts("");
            // puts("");
            for(int i=silef;i>=1;i--)
            {
                backmaxx[i]=max(backmaxx[i+1], cost[lefkey[i]]);
            }
            while(id!=0)
            {
                if(!red[id])
                {
                    int nowsi=sikey[id];
                    ll backmax=backmaxx[nowsi+1];
                    // cout<<id<<endl;
                    // cout<<backmax<<" "<<high[id]<<endl;
                    ans=min(ans, max(backmax, high[id]));
                }
                id=fff[id];
            }
            for(int i=1;i<=k;i++) kk[key[i]]=0;
            cout<<ans<<'\n';
        }
    }
    return 0;
}
/*
2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 13812kb

input:

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

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 1944ms
memory: 57104kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
66903787
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
57081624
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164...

result:

wrong answer 3rd lines differ - expected: '0', found: '66903787'