YbtOJ 664「可持久化数据结构」进制路径

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1e5+100,p=1e9+7;
int n,m,vis[N],Pr[N],fir[N],nxt[N<<1],son[N<<1],w[N<<1],tot,rt[N],b[N];
class ChairmanTree{
    private:
        int cnt;struct node{int l,r,v,s;}T[N*200];
        #define mid (l+r>>1)
        #define LT l,mid
        #define RT mid+1,r
        #define PT CI l=0,CI r=N-1
        I void PU(CI x){T[x].s=T[T[x].l].s+T[T[x].r].s,T[x].v=(T[T[x].r].v+T[T[x].l].v)%p;}
    public:
        I int S(CI p){return T[p].s;} 
        I int Q(CI p){return T[p].v;};
        I bool O(CI x,CI y,PT){if(l==r) return T[x].v>T[y].v;return T[T[x].r].v==T[T[y].r].v?O(T[x].l,T[y].l,LT):O(T[x].r,T[y].r,RT);}
        I int QS(CI x,CI L,CI R,PT){if(L<=l&&r<=R) return T[x].s;RI X=0;return L<=mid&&(X+=QS(T[x].l,L,R,LT)),R>mid&&(X+=QS(T[x].r,L,R,RT)),X;}
        I int F(CI x,CI v){RI l=v,r=N,X=v;W(l<=r) QS(x,v,mid)<=mid-v?X=mid,r=mid-1:l=mid+1;return X;}
        I void U0(int& x,CI L,CI R,PT){if(T[++cnt]=T[x],x=cnt,L<=l&&r<=R) return void(x=0);L<=mid&&(U0(T[x].l,L,R,LT),0),R>mid&&(U0(T[x].r,L,R,RT),0),PU(x);}
        I void U1(int& x,CI p,PT){if(T[++cnt]=T[x],x=cnt,l==r) return T[x].s=1,(void)(T[x].v=b[l]);p<=mid?U1(T[x].l,p,LT):U1(T[x].r,p,RT),PU(x);}
        I int A(CI x,CI v){RI t=F(x,v),w=x;v^t&&(U0(w,v,t-1),0);U1(w,t);return w;}
}T;
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z;}
#define to son[i]
struct node{int x,rt;}u;
I bool operator < (Cn node& A,Cn node& B){return T.O(A.rt,B.rt);}
priority_queue<node> q;
int s,t;I void Prt(CI x,CI d){x==s?writeln(d),write(x),pc(' '):(Prt(Pr[x],d+1),write(x),pc(' '));}
int main(){
    freopen("base.in","r",stdin),freopen("base.out","w",stdout);
    RI i,x,y,z;for(read(n,m,s,t),i=1;i<=m;i++) read(x,y,z),Add(x,y,z),Add(y,x,z);for(b[0]=i=1;i<N;++i) b[i]=(1ll*b[i-1]<<1)%p;
    q.push((node){s,rt[s]});W(!q.empty()) if(u=q.top(),q.pop(),!vis[u.x])
        for(vis[u.x]=1,u.x==t&&(writeln(T.Q(rt[t])),Prt(t,1),pc('\n'),clear(),exit(0),0),i=fir[u.x];i;i=nxt[i])
            x=T.A(u.rt,w[i]),(!rt[to]T.O(rt[to],x))&&(q.push((node){to,rt[to]=x}),Pr[to]=u.x);
    return writeln(-1),clear(),0;
}