提交记录

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=200005;
int n,L,q;
struct Edge{int v,a,z;
    Edge(int v=0,int a=0,int z=0):v(v),a(a),z(z){}
};vector<Edge>G[maxn];

struct Matrix{int a[2][2];
    Matrix(){memset(a,inf,sizeof(a));}
    int* operator[](int x){return a[x];}
    const int* operator[](int x)const{return a[x];}
};
Matrix operator*(const Matrix&a,const Matrix&b){
    Matrix c;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
    return c;
}

int siz[maxn],pa[maxn],dep[maxn],son[maxn];
int top[maxn],id[maxn],pos[maxn],dfn;
Matrix g[maxn][2];

void dfs1(int u,int fa){
    siz[u]=1;pa[u]=fa;dep[u]=dep[fa]+1;
    son[u]=0;
    for(Edge&e:G[u])if(e.v!=fa){
        int v=e.v,a=e.a,z=e.z;
        int typ=(z>=0);

        g[v][1][0][0]=min(a,L+a-z);
        g[v][1][0][1]=g[v][1][1][1]=a-z;
        g[v][1][1][0]=L+a-z;

        g[v][0][0][0]=min(a,L+a+z);
        g[v][0][0][1]=g[v][0][1][1]=a+z;
        g[v][0][1][0]=L+a+z;

        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
void dfs2(int u,int r){
    id[u]=++dfn;pos[dfn]=u;
    top[u]=r;
    if(son[u])
        dfs2(son[u],r);
    for(Edge&e:G[u])if(e.v!=pa[u]&&e.v!=son[u])
        dfs2(e.v,e.v);
}


#define ls (o<<1)
#define rs (o<<1|1)
struct SegmentTree{
    Matrix s[524300][2];
    void build(int o,int L,int R){
        if(L==R){
            s[o][0]=g[pos[L]][0];
            s[o][1]=g[pos[L]][1];
            return;
        }
        int M=(L+R)>>1;
        build(ls,L,M);
        build(rs,M+1,R);
        s[o][0]=s[ls][0]*s[rs][0];
        s[o][1]=s[ls][1]*s[rs][1];
    }
    Matrix query(int o,int L,int R,int ql,int qr,int k){
        if(ql<=L&&R<=qr)return s[o][k];
        int M=(L+R)>>1;
        if(qr<=M)return query(ls,L,M,ql,qr,k);
        if(M<ql)return query(rs,M+1,R,ql,qr,k);
        if(k==0) return query(rs,M+1,R,ql,qr,k)*query(ls,L,M,ql,qr,k);
        else return query(ls,L,M,ql,qr,k)*query(rs,M+1,R,ql,qr,k);
    }
}T;

Matrix query(int a,int b){
    Matrix A,B;
    A[0][0]=A[1][1]=B[0][0]=B[1][1]=0;
    while(top[a]!=top[b]){
        if(dep[top[a]]>dep[top[b]])
            A=T.query(1,1,n,id[top[a]],id[a],0)*A,a=pa[top[a]];
        else
            B=B*T.query(1,1,n,id[top[b]],id[b],1),b=pa[top[b]];
    }
    if(dep[a]>dep[b])A=T.query(1,1,n,id[b]+1,id[a],0)*A;
    else             B=B*T.query(1,1,n,id[a]+1,id[b],1);
    return A*B;
}

int main(){
    cin>>n>>L>>q;
    for(int i=1,a,b,c,d,typ;i<n;i++){
        cin>>a>>b>>c>>d>>typ;
        if(!typ)swap(a,b);
        G[a].push_back(Edge(b,c,d));
        G[b].push_back(Edge(a,c,-d));
    }
    dfs1(1,0);
    dfs2(1,1);
    T.build(1,1,n);
    for(int a,b;q--;){
        cin>>a>>b;
        Matrix ans=query(a,b);
        cout<<min(ans[0][0],ans[1][0])<<endl;
    }
    return 0;
}