Day 8 模拟赛总结

Part.1 赛时历程

还是跟以前一样的做题步骤，把所有题都看了一眼，然后发现怎么几乎全都做过，而且还补过。除了 $T4$ 看着有点眼生。但还是非常经典。

从 $T1$ 开始写，我知道有一个 $O(|V|^2)$ 的做法，但是数据范围有点小，可以用 $O(nm)$ 过，所以我就写了一个单调队列优化的 $dp$。但改成另一个写法也比较简单。然后发现不知道为什么，写的十分有问题，调红了。最后写完代码又调了 $20mins$ 才调完。($8:51:12$)

$T2$ 我有非常深刻的印象，在之前的某次模拟赛被这道题硬控了很久才写完，而且还没过。这次看到后，我也只知道是一个贪心。于是我采用了如下的贪心策略：

首先对左端点排序，使得左边小的尽可能先填，然后把余下的拿去做右端点，按照一样的方法填。

然后就惊喜的发现没过大样例 并不惊喜，因为我知道这样贪在中间重复的时候会有问题，随后我开始使用人类智慧，调换左端点与右端点的顺序，发现把大样例过了，然后我在拼一个 $O(n \times 2^m)$ 的暴力，确保有一个保底。($9:33:17$)

$T3$ 一眼原题，从 $s$ 点跑一个最短路与最短路计数，在从 $t$ 点跑一个最短路与最短路计数，最后枚举相遇的点和边即可。$(10:03:15)$

$T4$ 很眼熟，感觉碰到过类似的题目，于是先做了一步转化：

将查找 [l,r] 的最近公共祖先，变为查找以某一个为祖先时所对应的区间数量 f。

很显然，在这一步之后，以某一个节点为最近公共祖先的区间数 $g$ 就可以表示为：

$g_u = f_u - \sum_{x \in S(u)} f_x$

其中 $S(u)$ 表示 $u$ 的子节点。

然后求 $f$ 就有好几种方法，我只想到了 $DSU\ on\ Tree$ 和 线段树合并。(其实两者殊归同途)，最终，经过艰难决定，我写了一个我可能会更加熟悉而且好维护的线段树合并。

然后花了 $40 mins$ 就写完了代码，进入痛苦的调试阶段，发现合并与初始化写的有点小问题，有调了 $20 mins$，最后写完了，但发现无法测大样例，原因是万恶的 $Window$ 系统栈空间有上限，我在做重链剖分时，由于 $dfs$ 递归层数过多，爆栈了，而我不会手动扩栈，开始坐牢。($11:32:41$)

后面的一点时间写点对拍检验 $T4$ 代码。

Part.2 赛后总结

自我感觉良好，估分 $100 + 55 + 100 + 100 = 355$

实际得分拉完了 $100 + 90 + 40 + 40 = 270$

赛后发现，$T4$ 没过的原因是 $long\ long$ 没开全，在两个 $int$ 相乘时没转为 $long\ long$ 类型，痛失 $60pts$。

$T3$ 丢分原因是，我在计算相遇的方案数时，没有平方，导致答案偏大，再次痛失 $60 pts$。

$T2$ 没想到神秘贪心能过这么多点，太神秘了。

挂分十分严重。

Part.4 改进

检查时，要把每个可能爆 $int$ 或 $long\ long$ 的地方都找到，避免神秘挂分。

以及计数题，或许可以手造几个小数据来检验一下，有没有神秘小问题。

这啥题啊。。。

开局看 A，一眼单调队列优化 dp，写，这个题面描述恶心的，读错了两个细节，20min 写完了调了 40min。写的 $O(nm)$ 100pts。

B，我觉得 $a_i$ 的数据范围还是有必要给一下的，反正想了 +inf 种 dp 方式，耗时至少 1h，完全没觉得这是一道返回贪心，后面想到了网络流建模的做法，草上次代码源遇到网络流就已经不会写 Dinic 了，到现在都没复习。最后写了个 $O(n^m)$ 的，预估 0pts。

C 这个题面描述更是感觉模糊不清，反正我读题是真读了 30+min 的，就一个无任何用处的样例而且整套题完全没有样例解释。反正最后凭自己的理解感觉这道题还是十分简单的，然后又写了 20min 左右吧，最大的和最小的样例过了，剩下那个没过（代码是我理解的题意的正确代码），我就红了，然后就完全没有想的欲望了，遂跳。

D 会 $O(n^2 \log n)$ 的做法，没啥时间了啊，我没写过倍增求 LCA 只知道什么原来，手搓树剖又肯定来不及了，遂没开这道题，回去继续想 B。

差不多就最后 30min 了吧，通过询问陈老师彻底理解 C 题题面。

？后面 3 道我是怎么做到一道都没想出来的，这一波是真该加练了。

B：感谢评测姬。

理想：最终幻想。

哎别把题往难了想，再练练阅读理解。

这么晚才交总结是因为去给我姐祝寿去了。

估分：50+10+60+0 实际：50+0+40+0

T1用了dequeue,超时了。T2暴力爆了（其实题解的贪心方法我也写了。。但没写对，只好写暴力，气飞）T3正常吧。T4赛时没调对，不然应该有40分左右。。

今日总结：

感觉还好，估分：100+35+30+40，实际：20+35+30+40；

第一题，我的思路很混杂，想了一个小时左右，想出了应该怎么做，但是 n^2 的单调队列优化DP常数有点爆炸，给我卡住了，只拿了二十分；

第二题，第三题和第四题，我都打了个暴力，其中第二题想的时间线最久，在想如何贪心，但是差一点想出返回贪心，只想出了按照 l 从小到大排列贪心。而另外两道题就是正常拿了暴力分数

expected(100,10,30,20)160 (30,10,0,0) T1: 开始看错题了，卡了1h，然后再两个小时的时候回来重新看题面，对了，但是是在原来的错误代码上面改，又因为这次大样例太水，所以dp值为n的，wa了（进食）读错题面后要重构代码，不要史上拉使！！ T2： 想了40min，不会，写了贪心，感觉反悔贪心还挺重要的 T3: 想了20min，没想到dp，感觉不好做，打了暴力但爆了 T4: 想了40min，感觉挺可写得，想到st+二分的假做法，浪费了半个小时，然后写了个暴力

估分100+0+30+100实际100+5+30+100 T1场上一上来没看数据范围以为要o(p)做想了一个单调对列优化dp写了发现挂了原来是假了，发现p<=5000,写了p*p的做法得到了100分

/*
我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。
追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。
曾经的日子无法重来，我只不过是一个过客。
但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。
美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define se second
#define fi first
#define arr3 array<int,3>
const int N=1e4+6,M=2e5+6;
vector<arr3> g;
int dp[N];
map<pii,int> mp; 
int maxn=0;
int len[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,d,cnt;cin>>n>>m>>d>>cnt;
    f(i,1,cnt){
        int x,y,val;cin>>x>>y>>val;
        mp[make_pair(x,y)]+=val;
    }for(auto &x:mp){
        g.push_back({x.fi.se,x.fi.fi,x.se});
    }sort(g.begin(),g.end());
    cnt=g.size()-1;
    f(i,0,cnt){
        //cout<<g[i][0]<<" "<<g[i][1]<<"\n";
        dp[i]=g[i][2];
        f(j,0,i-1){
            if(abs(g[i][1]-g[j][1])<=abs(g[i][0]-g[j][0])*d)dp[i]=max(dp[i],dp[j]+g[i][2]);
        }maxn=max(maxn,dp[i]);
        //cout<<dp[i]<<" ";
        // list<int> q;int lst=-1;
        // //cout<<g[i].size()<<"\n";
        // f(j,0,len[i]-1){
        //     while(!q.empty()&&q.front()<g[i][j].fi-d){q.pop_front();}
        //     while(lst<g[i-1].size()&&g[i][j].fi>=g[i-1][lst+1].fi){
        //         lst++;while(!q.empty()&&dp[i-1][q.back()]<dp[i-1][lst]){q.pop_back();}
        //         q.push_back(lst);
        //     }
        //     if(q.size()==0)dp[i].push_back(g[i][j].se);
        //     else dp[i].push_back(dp[i-1][lst]+g[i][j].se);
        //     maxn=max(maxn,dp[i][j]);
        // }
        // q.clear();lst=len[i-1];
        // rep(j,len[i]-1,0){
        //     while(!q.empty()&&q.front()>g[i][j].fi|+d){q.pop_front();}
        //     while(lst>0&&g[i][j].fi<=g[i-1][lst-1].fi){
        //         lst--;while(!q.empty()&&dp[i-1][q.back()]<dp[i-1][lst]){q.pop_back();}
        //         q.push_back(lst);
        //     }
        //     if(q.size()==0)dp[i][j]=max(dp[i][j],g[i][j].se);
        //     else dp[i][j]=max(dp[i-1][q.front()]+g[i][j].se,dp[i][j]);
        //     //cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        //     maxn=max(maxn,dp[i][j]);
        // }

    }cout<<maxn;
    return 0;
}
/*
I often look back on the past.
Moments of life are frozen in my mind. I cut, fold, and curl the time behind me, kneading it into the white clouds in the sky.
Even clouds differ among themselves: cumulus clouds are heavy, while cirrus clouds are ethereal. The stunning scenes of life sweep through my thoughts and remain unforgettable for a lifetime, whereas more ordinary, everyday memories leave behind only fragments under the erosion of time.

Recollection is like entering a dream: too clear, and it cannot delight my fancy; too vague, and it sinks into nothingness. Only the mountains and waters in thin mist, the woman behind a veil—that恰到好处的 haziness—can satisfy my aesthetic fastidiousness.

Recollection always wraps me, unbidden, in yellowed pages. Friends parted and reunited, streets demolished and rebuilt—all these clues help me start from a specific moment and sail upstream along the river of time.
Those days cannot be relived; I am merely a passerby.
Yet I still long to take a moment of leisure on every journey of remembrance, to pause before a scene, to gaze at my past self through the mist of years, and to savor as much sweetness as possible.
If beautiful times once flowed through my body, I am content.

The past has solidified; I move forward with my memories, but I often neglect to tend to them, and the memories themselves keep changing their forms. This brings some challenge to my journeys of recollection.
Where should I pause? I ask myself.
*/

T2 发现去年见过但是记得是贪心过不了，因为我只记得场上写了个贪心wa了，感觉不能做就跳了，最后乱搞得了5分

/*
我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。
追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。
曾经的日子无法重来，我只不过是一个过客。
但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。
美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define se second
#define fi first
const int N=2e5+6,M=2e5+6;
vector<pii> g[N];
int a[N];
struct node{
    int l,r;
}x[N];
bool cmp(node u,node v){if(u.l!=v.l)return u.l<v.l;else return u.r<v.r;}
bool cmp1(node u,node v){if(u.r!=v.r)return u.r<v.r;else return u.l<v.l;}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;cin>>n>>m;
    f(i,1,n)cin>>a[i];
    f(i,1,m)cin>>x[i].l>>x[i].r;
    sort(x+1,x+1+m,cmp);
    int ans=0;
    int ll=1,rr=n;
    f(i,1,m){
        while(a[ll]==0)ll++;while(a[rr]==0)rr--;
        if(a[ll]>0&&x[i].l>=ll){a[ll]--;ans++;continue;}
        if(a[rr]>0&&x[i].r>=n-rr+1){a[rr]--;ans++;continue;}
    }
    int now=0;
    sort(x+1,x+1+m,cmp1);
    ll=1,rr=n;
    f(i,1,m){
        while(a[ll]==0)ll++;while(a[rr]==0)rr--;
        if(a[rr]>0&&x[i].r>=n-rr+1){a[rr]--;now++;continue;}
        if(a[ll]>0&&x[i].l>=ll){a[ll]--;now++;continue;}
    }
    ans=max(ans,now);
    now=0;
    sort(x+1,x+1+m,cmp1);
    ll=1,rr=n;
    f(i,1,m){
        while(a[ll]==0)ll++;while(a[rr]==0)rr--;
        if(a[ll]>0&&x[i].l>=ll){a[ll]--;now++;continue;}
        if(a[rr]>0&&x[i].r>=n-rr+1){a[rr]--;now++;continue;}
    }//cout<<now<<"\n";
    ans=max(ans,now);
    now=0;
    sort(x+1,x+1+m,cmp);
    ll=1,rr=n;
    f(i,1,m){
        while(a[ll]==0)ll++;while(a[rr]==0)rr--;
        if(a[rr]>0&&x[i].r>=n-rr+1){a[rr]--;now++;continue;}
        if(a[ll]>0&&x[i].l>=ll){a[ll]--;now++;continue;}
    }//cout<<now<<"\n";
    ans=max(ans,now);
    cout<<ans;
    return 0;
}/*
I often look back on the past.
Moments of life are frozen in my mind. I cut, fold, and curl the time behind me, kneading it into the white clouds in the sky.
Even clouds differ among themselves: cumulus clouds are heavy, while cirrus clouds are ethereal. The stunning scenes of life sweep through my thoughts and remain unforgettable for a lifetime, whereas more ordinary, everyday memories leave behind only fragments under the erosion of time.

Recollection is like entering a dream: too clear, and it cannot delight my fancy; too vague, and it sinks into nothingness. Only the mountains and waters in thin mist, the woman behind a veil—that恰到好处的 haziness—can satisfy my aesthetic fastidiousness.

Recollection always wraps me, unbidden, in yellowed pages. Friends parted and reunited, streets demolished and rebuilt—all these clues help me start from a specific moment and sail upstream along the river of time.
Those days cannot be relived; I am merely a passerby.
Yet I still long to take a moment of leisure on every journey of remembrance, to pause before a scene, to gaze at my past self through the mist of years, and to savor as much sweetness as possible.
If beautiful times once flowed through my body, I am content.

The past has solidified; I move forward with my memories, but I often neglect to tend to them, and the memories themselves keep changing their forms. This brings some challenge to my journeys of recollection.
Where should I pause? I ask myself.
*/

先看了t4发现可以做，先转化了一下，发现lca不好刻画，于是转化为到跟的连上的和于是点权变成了x[u]-x[fa];发现可以用dsuontree用set维护区间贡献为（r-l+1)*(r-l+2)/2;

/*
我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。
追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。
曾经的日子无法重来，我只不过是一个过客。
但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。
美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define se second
#define fi first
#define arr3 array<int,3>
const int N=2e5+6,M=2e5+6;
vector<int> g[N];
int a[N],v[N];
int gx[N];int sz[N];
int zx[N];
void dfs(int x,int fa){
    gx[x]=v[x]-v[fa];//5 3
    sz[x]=1;    
    for(int u:g[x]){
        if(u==fa)continue;
        dfs(u,x);
        if(sz[u]>sz[zx[x]]){zx[x]=u;}
        sz[x]+=sz[u];
    }
}int id[N];
int sum;set<pii> st[N];
int ans[N];int n;
void merge(int x,int l,int r){
    auto id=st[x].upper_bound({l,n+1});
    int nl=l,nr=r;
    if(id!=st[x].begin()){
        id=prev(id);
        int ll=(*id).fi,rr=(*id).se;
        if(rr==l-1){
            nl=ll;
            st[x].erase(id);//pii tep={ll,r};
            ans[x]-=(rr-ll+1)*(rr-ll+2)/2;
            //st[x].insert(tep);int len=tep.se-tep.fi+1;
            //ans[x]+=len*(len+1)/2;
        }
    }id=st[x].lower_bound({r,0});
    if(id!=st[x].end()){
        int ll=(*id).fi,rr=(*id).se;
        if(ll==r+1){
            nr=rr;
            st[x].erase(id);//pii tep={ll,r};
            ans[x]-=(rr-ll+1)*(rr-ll+2)/2;
            //st[x].insert(tep);int len=tep.se-tep.fi+1;
            //ans[x]+=len*(len+1)/2;
        }
    }

    //cout<<nl<<" "<<nr<<"\n";
    ans[x]+=(nr-nl+2)*(nr-nl+1)/2;
    st[x].insert({nl,nr});
}
//123 1234
//n*(n+1)/2
void dfs1(int x,int fa){
    for(int u:g[x]){
        if(u==fa)continue;
        dfs1(u,x);
    }swap(st[x],st[zx[x]]);ans[x]=ans[zx[x]];
    merge(x,id[x],id[x]);
    for(int u:g[x]){
        if(u==fa||u==zx[x])continue;
        if(st[u].size()>st[x].size()){
            for(pii tp:st[u]){
                merge(x,tp.fi,tp.se);
            }
        }else{
            for(pii tp:st[x]){
                merge(u,tp.fi,tp.se);
            }swap(st[u],st[x]);swap(ans[u],ans[x]);
        }
    }sum+=ans[x]*gx[x];
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    f(i,2,n){int x;cin>>x;g[x].push_back(i);g[i].push_back(x);}
    f(i,1,n)cin>>a[i],id[a[i]]=i;
    f(i,1,n)cin>>v[i];
    dfs(1,-1);
    dfs1(1,-1);
    cout<<sum;
    return 0;
}/*
I often look back on the past.
Moments of life are frozen in my mind. I cut, fold, and curl the time behind me, kneading it into the white clouds in the sky.
Even clouds differ among themselves: cumulus clouds are heavy, while cirrus clouds are ethereal. The stunning scenes of life sweep through my thoughts and remain unforgettable for a lifetime, whereas more ordinary, everyday memories leave behind only fragments under the erosion of time.

Recollection is like entering a dream: too clear, and it cannot delight my fancy; too vague, and it sinks into nothingness. Only the mountains and waters in thin mist, the woman behind a veil—that恰到好处的 haziness—can satisfy my aesthetic fastidiousness.

Recollection always wraps me, unbidden, in yellowed pages. Friends parted and reunited, streets demolished and rebuilt—all these clues help me start from a specific moment and sail upstream along the river of time.
Those days cannot be relived; I am merely a passerby.
Yet I still long to take a moment of leisure on every journey of remembrance, to pause before a scene, to gaze at my past self through the mist of years, and to savor as much sweetness as possible.
If beautiful times once flowed through my body, I am content.

The past has solidified; I move forward with my memories, but I often neglect to tend to them, and the memories themselves keep changing their forms. This brings some challenge to my journeys of recollection.
Where should I pause? I ask myself.
*/

T3场上想了一个不用容斥的做法，发现路径肯定是一条最短路中间一段两个人做不同的路，退了柿子发现又让disu<sum/2,disv>sum/2,也不会重复发现这个东西贡献可以做两次dij 但是感觉写起来恒麻烦,也不知道对不对,没有发现可以通过中间的点容斥，就没写只写了特殊性质

/*
我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。
追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。
曾经的日子无法重来，我只不过是一个过客。
但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。
美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define se second
#define fi first
const int N=2e5+6,M=2e5+6;
vector<pii> g[N];
int dis[N];
int vis[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,s,t;cin>>n>>m>>s>>t;
    f(i,1,m){
        int u,v,w;cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }priority_queue<pii,vector<pii>,greater<pii>> q;
    f(i,1,n)dis[i]=1e18;
    q.push({0,s});dis[s]=0;
    while(!q.empty()){
        int x=q.top().se;q.pop();
        //cout<<x<<" "<<dis[x]<<"\n";
        if(vis[x]==1)continue;vis[x]=1;
        for(pii u:g[x]){
            if(dis[u.fi]>dis[x]+u.se){
                dis[u.fi]=dis[x]+u.se;q.push({dis[u.fi],u.fi});
            }
        }
    }cout<<dis[t]<<"\n"<<0;
    return 0;
}/*
I often look back on the past.
Moments of life are frozen in my mind. I cut, fold, and curl the time behind me, kneading it into the white clouds in the sky.
Even clouds differ among themselves: cumulus clouds are heavy, while cirrus clouds are ethereal. The stunning scenes of life sweep through my thoughts and remain unforgettable for a lifetime, whereas more ordinary, everyday memories leave behind only fragments under the erosion of time.

Recollection is like entering a dream: too clear, and it cannot delight my fancy; too vague, and it sinks into nothingness. Only the mountains and waters in thin mist, the woman behind a veil—that恰到好处的 haziness—can satisfy my aesthetic fastidiousness.

Recollection always wraps me, unbidden, in yellowed pages. Friends parted and reunited, streets demolished and rebuilt—all these clues help me start from a specific moment and sail upstream along the river of time.
Those days cannot be relived; I am merely a passerby.
Yet I still long to take a moment of leisure on every journey of remembrance, to pause before a scene, to gaze at my past self through the mist of years, and to savor as much sweetness as possible.
If beautiful times once flowed through my body, I am content.

The past has solidified; I move forward with my memories, but I often neglect to tend to them, and the memories themselves keep changing their forms. This brings some challenge to my journeys of recollection.
Where should I pause? I ask myself.
*/

咋这样啊

估分：100+10+30+40 = 180

结局：80+10+40+0 = 130

在此我驳回之前的“最恼火的一集”的称号

排名更新了，现在这个更是恼火

T1

本来没啥思路，想着先打个dp再说，然后就发现可以单调队列优化一下。

写了30min，直接过了大洋里，然后仓皇提交。

不幸的事就这么发生了。（并没有觉得deque常数大到让我的代码时间爆炸）

T2

实在觉得过于困难了，话说2025csp-S也被反悔贪心卡住了

最终写了一个$O(n^m)$的暴力，幸好跑过去了。

T3

也不知道怎么做，糊了一个特殊点上去。

T4

最开始觉得好有可写性，然而写了一会过后就感觉不怎么会了。

关键是最后倍增LCA还写错了，雪上加霜。

终

┭┮﹏┭┮

T1

开了个1e8的数组，TLE了。改了就A了

T2

只能想到35分暴力

T3

感觉挺错的

但是不知道正确的怎么写

T4

暴力错了

不知道哪错了

个人觉得题目还好吧。

先看的 $\text{A}$ 题。扫了一眼题目（这不是水题吗，范围这么小），写了个错误代码后过了样例，交了一发。然后去看 $\text{B}$，$\text{B}$ 一眼贪心，但暂时没有思路，正在仔细思考。突然有人问到大样例在哪，我想了一下我好像也没有测大样例，去测了一下 $\text{A}$ 题的代码发现错了。我再重新细看 $\text{A}$ 题题面，发现居然还有纵向移动（我看成了横向移动 $\Delta$ 问最大，浪费 $10$ 分钟）。

我觉定先把 $\text{B}$ 先写了来再写 $\text{A}$。$\text{B}$ 花了一个小时写出来了一个很复杂的贪心过程，测了大样例，过了交。继续看 $\text{A}$，写了个用单调队列优化的一个东西，过了样例后测大样例，大样例跑了 $6$ 秒。我就想这个“暴力”应该没有什么问题，便去看 $\text{C}$。

$\text{C}$ 题输出的第一个答案比较好求（找最短路径的长度），我直接写了个 $\text{Dijkstra}$。答案对了后，想第二个不同路线方案数怎么求。想了又一个小时观察了一下大样例和样例，又灵机一动写出了如下代码：

auto _=dj(s,t);
cout<<_<<'\n'<<(_%2?0:2)<<'\n';//第二个的输出

又是只有人类才能想得出来的写法，目的就骗点分。赛后一看还真骗了 $10$ 分。

赛后发现这样写可以还能骗取到 $30$ 分：

auto _=dj(s,t);
cout<<_<<'\n'<<0<<'\n';

已哭晕。┭┮﹏┭┮

最后才看 $\text{D}$ 题，思考了一个小时后无思路，一看时间马上结束。我直接全部把节点的权值累加输出偏分，但没骗到分。

分数出来后发现 $\text{A}$ 题 RE 了。讨论后发现是 $x$，$y$ 整反了。

总结：以后做题一定要先把题目看清楚，在想思路和写代码。还有 depue 易被卡尽量避免用。

前言 “🈲🐘🔞”

总结

棒棒🍭题

一眼秒🤯🤯🤯。直接DP+单调队列优化！

无🍭题

9:00开题，想了一下，感觉可以对L排序，再反悔贪心，写完也是直接过了水水小样例，但大样例相差甚远，我当时怀疑自己写出了假做法，此时以为是本题是人均题就开始死磕。证明了一会，感觉十分正确，改了几版都没过，💩🗻代码已大成，10:30又重构了一次，还是错的。终于在11:00时发现————代码写错了🤡。可以埋了。

🍭🍭🍭题

没时间想，打了暴力，但挂了。

🍭🍭🍭🍭题

没时间想，打了暴力。

得分：100+100+0+20

评价：T2饭堂

餹粉：🍭完了

expected (100+10+100+10) 220
(100+35+100+0) 235
T1 30min
T2 1.5h
T3 1.5j
T4 30min
T4暴力有问题，WA，时间不够
T2写太慢了
没有学过返回贪心写不了T2
idk lmao