QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334175#6111. Two PathsFISHER_TL 6835ms61352kbC++145.9kb2024-02-21 12:30:402024-02-21 12:30:40

Judging History

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

  • [2024-02-21 12:30:40]
  • 评测
  • 测评结果:TL
  • 用时:6835ms
  • 内存:61352kb
  • [2024-02-21 12:30:40]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5,Maxk=5e5;
 
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
 
int n,m,fa[Maxn+5]; ll dis[Maxn+5];
int dfn[Maxn+5],st[Maxn+5][20],cur;
vector<pair<int,int>> v[Maxn+5];
 
inline int Get(int x,int y) {return (dfn[x]<dfn[y])?x:y;}
inline int LCA(int x,int y)
{
    if(x==y) return x; if((x=dfn[x])>(y=dfn[y])) swap(x,y);
    int len=__lg(y-x++); return Get(st[x][len],st[y-(1<<len)+1][len]);
}
inline ll Dis(int x,int y) {return dis[x]+dis[y]-2*dis[LCA(x,y)];}
 
struct Node{int x,y;} f[Maxn+5],g[Maxn+5];
inline Node operator+(Node a,Node b)
{
    if(a.x==0 && a.y==0) return b; if(b.x==0 && b.y==0) return a;
    int ax=a.x,ay=a.y,bx=b.x,by=b.y;
    ll s1=Dis(ax,ay),s2=Dis(bx,by),s3=Dis(ax,bx),s4=Dis(ay,by),s5=Dis(ax,by),s6=Dis(ay,bx);
    ll mx=max(s1,max(s2,max(s3,max(s4,max(s5,s6)))));
    if(mx==s1) return Node{ax,ay}; if(mx==s2) return Node{bx,by};
    if(mx==s3) return Node{ax,bx}; if(mx==s4) return Node{ay,by};
    if(mx==s5) return Node{ax,by}; if(mx==s6) return Node{ay,bx};
}
inline void dfs(int x,int f)
{
    fa[x]=f,dfn[x]=++cur,st[cur][0]=f;
    for(auto [y,z]:v[x]) if(y!=f) dis[y]=dis[x]+z,dfs(y,x);
}
inline void dfs1(int x,int fa)
{f[x]=Node{x,x}; for(auto [y,z]:v[x]) if(y!=fa) dfs1(y,x),f[x]=f[x]+f[y];}
inline void dfs2(int x,int fa)
{
    static Node pr[Maxn+5],sf[Maxn+5];
    Node res=g[x]+Node{x,x}; for(auto [y,z]:v[x]) if(y!=fa) pr[y]=res,res=res+f[y];
    res=Node{0,0}; reverse(v[x].begin(),v[x].end());
    for(auto [y,z]:v[x]) if(y!=fa) sf[y]=res,res=res+f[y];
    reverse(v[x].begin(),v[x].end());
    for(auto [y,z]:v[x]) if(y!=fa) g[y]=pr[y]+sf[y];
    for(auto [y,z]:v[x]) if(y!=fa) dfs2(y,x);
}
 
inline int Check1() {For(i,1,n) if(v[i].size()>2) return 0; return 1;}
namespace T1
{
    struct Point
    {
        ll x,y; inline Point() {}
        inline Point(ll _x,ll _y): x(_x),y(_y) {}
    }; vector<Point> t[Maxn*4+5];
    inline bool operator<(Point a,Point b)
    {return a.x<b.x || (a.x==b.x && a.y<b.y);}
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    int rt,rk[Maxn+5],id[Maxn+5],h[Maxn+5],tot; ll sum[Maxn+5];
    int mn[Maxn+5][20];
    inline void dfs(int x,int f,int k)
    {
        id[++tot]=x,rk[x]=tot,h[tot]=k;
        for(auto [y,z]:v[x]) if(y!=f) dfs(y,x,z);
    }
    inline int Get(int l,int r)
    {int len=__lg(r-l+1); return min(mn[l][len],mn[r-(1<<len)+1][len]);}
    inline double Slope(Point a,Point b) {return 1.0*(b.y-a.y)/(b.x-a.x);}
    inline auto Merge(vector<Point> v1,vector<Point> v2)
    {
        vector<Point> v3,v;
        for(auto i:v1) v3.push_back(i);
        for(auto i:v2) v3.push_back(i);
        sort(v3.begin(),v3.end());
        for(auto i:v3)
        {
            while(v.size()>1 && Slope(v[v.size()-2],v.back())<=
                 Slope(v.back(),i)) v.pop_back();
            v.push_back(i);
        } return v;
    }
    inline void Build(int l,int r,int p)
    {
        if(l==r) {t[p].push_back(Point(sum[l+1],sum[l])); return;}
        int mid=(l+r)>>1; Build(l,mid,ls(p)),Build(mid+1,r,rs(p));
        t[p]=Merge(t[ls(p)],t[rs(p)]);
    }
    inline ll Get(int p,int A,int B)
    {
        vector<Point> &v=t[p]; int sz=v.size(); double res=1.0*B/A;
        int l=0,r=sz-1; while(l<r)
        {
            int mid=(l+r+1)/2;
            if(Slope(v[mid-1],v[mid])>=res) l=mid;
            else r=mid-1;
        } auto [x,y]=v[l]; return 1ll*A*y-1ll*B*x;
    }
    inline ll Count(int nl,int nr,int l,int r,int p,int A,int B)
    {
        if(l<=nl && nr<=r) return Get(p,A,B);
        int mid=(nl+nr)>>1; ll res=LLONG_MIN;
        if(l<=mid) res=max(res,Count(nl,mid,l,r,ls(p),A,B));
        if(r>mid) res=max(res,Count(mid+1,nr,l,r,rs(p),A,B));
        return res;
    }
    inline void Run()
    {
        For(i,1,n) if(v[i].size()==1) {rt=i; break;}
        dfs(rt,0,0); For(i,1,n) sum[i]=sum[i-1]+h[i];
        For(i,1,n) mn[i][0]=h[i];
        For(j,1,19) for(int i=1;i+(1<<j)-1<=n;++i)
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
        Build(1,n,1);
        while(m--)
        {
            int x=rk[read()],y=rk[read()],A=read(),B=read();
            if(x>y) swap(x,y),swap(A,B);
            ll res=sum[x]*A+(sum[n]-sum[y])*B;
            res=max(res,(sum[y]-sum[x+1])*B+sum[x]*A);
            res=max(res,(sum[n]-sum[y])*B+(sum[y-1]-sum[x])*A);
            ll now=Count(1,n,x,y-1,1,A,B);
            now=now-sum[x]*A+sum[y]*B; res=max(res,now);
            printf("%lld\n",res);
        }
        // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    }
}
 
int main()
{
    // freopen("C.in","r",stdin);
    // freopen("C.out","w",stdout);
 
    n=read(),m=read();
    For(i,1,n-1)
    {
        int a=read(),b=read(),c=read();
        v[a].emplace_back(b,c),v[b].emplace_back(a,c);
    }
    if(Check1()) {T1::Run(); return 0;}
    dfs(1,0);
    For(j,1,19) for(int i=1;i+(1<<j)-1<=n;++i)
        st[i][j]=Get(st[i][j-1],st[i+(1<<j-1)][j-1]);
    dfs1(1,0),dfs2(1,0);
    while(m--)
    {
        int x=read(),y=read(),A=read(),B=read(),l=LCA(x,y);
        ll ans=0;
        for(int i=x;i!=l;i=fa[i])
        {
            Node a=f[i],b=g[i];
            ll dx=max(Dis(x,a.x),Dis(x,a.y));
            ll dy=max(Dis(y,b.x),Dis(y,b.y));
            ans=max(ans,dx*A+dy*B);
        }
        for(int i=y;i!=l;i=fa[i])
        {
            Node a=f[i],b=g[i];
            ll dx=max(Dis(x,b.x),Dis(x,b.y));
            ll dy=max(Dis(y,a.x),Dis(y,a.y));
            ans=max(ans,dx*A+dy*B);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 38844kb

input:

6 4
1 2 4
2 5 5
2 3 7
3 6 5
3 4 4
1 4 1 1
1 4 2 1
5 6 1 1
5 6 1 10

output:

18
32
18
160

result:

ok 4 number(s): "18 32 18 160"

Test #2:

score: 0
Accepted
time: 4ms
memory: 31292kb

input:

2 1
1 2 1
1 2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 3ms
memory: 30216kb

input:

2 10
1 2 2
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 3 1
1 2 3 2
1 2 3 3
1 2 2 3
1 2 1 3

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 77ms
memory: 30856kb

input:

10 500000
4 5 576
5 8 218
1 10 678
1 9 2540
7 8 2023
2 7 5510
2 9 8454
4 6 22
3 9 5248
2 5 35782 82142
1 2 95412 85188
4 5 82466 22193
3 6 22169 67901
4 10 67229 30987
1 10 68282 17858
1 8 53726 3246
5 8 13913 74110
2 8 30052 7204
1 4 95255 48216
2 5 41392 98997
3 8 8435 5947
1 5 22067 21610
7 9 343...

output:

674365186
1454303268
477920681
1359445921
1501996827
1320778726
889342640
1582045824
426346196
1792561801
789005461
166905972
478560756
71705653
343648830
901237204
420263788
1710700661
309792440
335240094
1852278021
1679904905
1055408048
1644275016
563316675
602184744
873340490
815015664
1356022267...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 189ms
memory: 27328kb

input:

100 500000
4 63 6394
57 91 2108
5 52 9292
6 63 3151
52 62 1006
13 19 8138
42 59 6102
3 95 275
36 80 8426
20 84 7879
32 100 4423
71 89 9590
55 98 240
46 100 7470
70 92 7417
43 54 6092
24 41 230
93 94 6591
8 92 2558
34 63 7534
4 36 5620
17 93 987
35 96 1288
42 68 6280
72 89 9818
43 57 8266
26 62 2431
...

output:

30730511688
35868047826
94569561805
103860674856
108734641138
103921529851
151172279864
108994447520
79859941598
90637244010
113651189677
26614889256
54138181416
163935808262
43257729984
101945300646
27547811269
67543514171
84292164869
59484837480
117300068794
77146438694
27400485192
55424042658
628...

result:

ok 500000 numbers

Test #6:

score: 0
Accepted
time: 6180ms
memory: 60544kb

input:

200000 500000
83239 106513 1257
142726 196994 1263
95614 142588 7488
88575 193932 8123
31396 180633 1564
37559 131657 927
143893 157390 740
117889 182920 7831
103309 142289 6864
15478 36228 2717
5896 6815 5902
42275 184396 2646
21903 63571 8966
23873 42450 2721
36540 46154 9467
155293 161123 8588
54...

output:

5966882576104305
7271792958583645
8570461339781342
9614114352538144
6712681170527500
9409581586879995
6304678086998919
6559831613756394
4016495625693024
4381351843519688
4971908463803118
8759545709797016
11418325924391126
8912046248703475
10780907424911508
3112723787504739
9395431732704804
851233289...

result:

ok 500000 numbers

Test #7:

score: 0
Accepted
time: 71ms
memory: 38832kb

input:

10 500000
7 8 6474
3 4 6652
4 5 5193
6 9 457
5 9 3937
1 7 7261
2 5 6472
6 8 6967
3 10 8997
2 9 77462 28703
3 7 31026 16732
2 6 39340 36431
6 9 95641 333
4 8 17377 97247
2 4 20769 98147
4 6 425 42124
4 8 53119 54974
2 4 49307 3731
1 7 13417 95608
7 8 36330 40656
6 10 16594 36336
1 6 47819 1121
1 3 93...

output:

2723123845
841480408
1828727322
1988211389
2006138424
2972774483
878701873
1811610573
1614909795
3697830616
1573037298
1336010492
685083521
3657916506
2557058802
3370810317
3011684921
862077669
2124928512
3326043566
1360831395
1603107540
3131147303
1037179764
1973141216
1587191713
747094784
36277104...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 178ms
memory: 38536kb

input:

100 500000
40 72 2893
46 57 7594
13 90 4014
32 59 8870
4 81 4432
59 94 8856
59 96 4895
96 100 9950
32 80 8362
5 89 1777
36 69 2134
24 62 9978
21 65 3506
49 61 6056
33 48 5740
1 30 4143
30 60 8914
60 70 4900
66 93 6395
10 68 1687
10 95 2472
4 20 3135
2 17 9637
56 78 4429
20 27 2053
52 89 6906
27 39 9...

output:

106913710770
4495733708
102758976134
80160799892
76732267750
47039029473
72520507589
73042063332
73155659164
70949908024
18019999665
55814535350
72254712051
121025392740
66270956091
135577152247
39206666175
97754289402
83622700164
89895046420
147890155522
62926235281
108657350392
100238158900
814086...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 6224ms
memory: 60112kb

input:

200000 500000
72622 96340 7225
16757 66347 2999
101297 187932 6437
49037 154632 460
124025 196592 9940
153072 170123 1421
34394 199313 4817
32364 32518 5106
88700 199062 8686
31819 36499 9765
52871 159318 6576
1498 113000 6088
87532 137708 9913
18424 42545 9372
10501 33545 5958
23767 170025 2704
187...

output:

14850031235173232
6999821359673356
13994322220418811
15658897860429808
5566180270698198
7768919631255131
7795054483438192
7419776394069074
12641505965465227
7472188388977804
15268455327661860
10901394489199617
8199280990426768
12441824458056512
5059765147523162
8301785128173369
6921399963160754
9272...

result:

ok 500000 numbers

Test #10:

score: 0
Accepted
time: 75ms
memory: 38588kb

input:

10 500000
7 8 6564
4 8 6189
3 9 5516
2 4 8374
2 9 4364
7 10 7523
6 8 9898
5 8 7016
1 5 2345
5 8 51845 42560
4 5 55887 98340
3 8 49610 54530
9 10 22945 35062
3 8 3458 95253
3 6 23153 11481
1 8 34851 37986
5 9 87362 27198
1 7 55997 43106
1 7 75611 27271
7 8 71599 78148
6 7 34117 75458
2 4 79390 55048
...

output:

1161870605
3095430318
1673745050
1133235480
1802853531
892085090
1010217393
2190048410
2217209026
2761113977
2448810841
2339726206
1900526448
2923869030
1282299167
2882083522
2590862660
2125646342
2738520864
1608180381
1666730547
2125172192
2345809770
1603963890
3685256440
2391830675
183542487
93557...

result:

ok 500000 numbers

Test #11:

score: 0
Accepted
time: 150ms
memory: 38668kb

input:

100 500000
64 80 6288
35 50 3079
47 52 1840
5 69 4588
3 14 5154
76 80 5382
35 60 9496
19 61 9625
71 73 9786
7 46 9867
5 15 9846
14 57 7663
39 52 9476
21 38 3153
44 63 1358
60 67 4899
56 59 302
8 52 104
50 56 2937
28 72 8543
85 91 7835
16 87 5283
29 77 3795
11 84 6769
49 65 1585
45 51 1354
2 89 9853
...

output:

72202925787
97514852513
56756195638
37288713475
35676803180
90017144414
38927158215
28601206274
14400684154
45932515989
77207561276
59432631660
70376380240
78182150824
76907451131
97790656742
61036431338
66756945882
44962902462
95491099215
84137846038
57887416052
58421189377
45768814245
47300757994
...

result:

ok 500000 numbers

Test #12:

score: 0
Accepted
time: 6835ms
memory: 61352kb

input:

200000 500000
84618 98845 7176
107087 196559 4404
173709 192096 4717
122383 132949 1263
13177 34882 5439
139807 160157 1421
45167 91345 9766
107962 187717 2148
66125 151170 6686
63358 86085 5420
92294 134701 5058
113293 149067 2818
52824 164065 9708
44586 64319 6527
52176 147205 1116
36120 153708 18...

output:

10077660798661166
6673502274389958
12939177208895010
9047200007665110
6573554974664500
5242597508990838
13676616292679150
9704815634833183
11561184450694770
12472403863791083
13122447381660824
13320490331795583
8658969745868196
8796014087160251
13063721599988841
12566284718749275
7973072528332602
11...

result:

ok 500000 numbers

Test #13:

score: 0
Accepted
time: 72ms
memory: 38912kb

input:

10 500000
5 10 9359
6 8 2622
3 4 32
1 5 6291
2 5 4790
6 7 9273
5 7 7916
2 3 1256
7 9 6094
1 4 93524 56417
1 4 72235 21165
1 8 59881 96821
3 7 60649 69792
3 7 40702 86345
2 7 89678 55741
3 7 83505 90656
9 10 91223 25352
6 10 12287 11104
5 8 94433 78823
4 6 19397 21614
2 6 56138 89726
3 7 87392 7152
2...

output:

2513828544
1912738490
2824268570
1764473685
1654088085
1931893217
2364747645
2037769347
362591929
2301745394
631573827
2454351592
1431346800
1917618468
112297763
185018940
1653764936
1250254372
1568465383
1292309244
236168002
506864435
425491147
2028002330
476710384
1808277470
2247989250
1318111291
...

result:

ok 500000 numbers

Test #14:

score: 0
Accepted
time: 185ms
memory: 38584kb

input:

100 500000
8 10 4275
5 60 2756
55 71 6562
46 53 306
40 85 8980
24 97 1909
59 90 8289
58 77 9299
38 74 9722
5 95 9173
34 42 7558
35 92 8051
78 86 5446
29 63 4443
72 78 3872
26 100 246
35 50 203
73 74 2605
53 74 6774
66 81 6888
39 66 4686
31 62 4727
3 92 9440
71 88 4918
18 90 9628
22 46 9995
28 49 991...

output:

65913039086
86901503285
145182328228
51391603893
107334514650
33026739520
141561395797
94885846572
85557851805
95450858526
43327973728
76933550118
105576354578
116690159952
127214406241
57156892577
92243211803
2929303556
60914681674
87520089774
88616664175
89811058923
60767857476
39044073040
6597593...

result:

ok 500000 numbers

Test #15:

score: -100
Time Limit Exceeded

input:

200000 500000
48263 193405 8782
39826 138335 6086
43411 47049 42
32460 100163 6561
110839 195838 6052
5325 169299 7212
2594 89322 851
46973 138509 8277
45626 176835 6893
94589 172557 9834
46014 69648 1541
10815 31117 7070
123771 141531 2871
72939 179823 4185
68124 69369 7576
127353 144997 9295
96779...

output:

4813047735928155
13563121456000208
10623977740697384
12368325537868986
9906634169705396
15509065513494903
5103499979323596
12246478270010336
14933318539416384
8682385540396731
6020406730020679
14413092183185878
12398399473755534
14259938583507292
11726545588336542
12617036028393990
11053303327631314...

result: