DZY 's BLOG

经典的开关问题的树上的版本。

还是赤果果的高斯消元。

多了一个细节是求出sigma(x[i])的最小值。

先跑高斯消元。得到倒三角矩阵之后。考虑到n=100。而且不确定位应该不会太多。（不然怎么过啊哦擦）。所以可以把每种解都跑出来。保留最小值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int a[110][110],x[110],n,An = 1000000009;
void dfs(int k,int sum){
    if(sum >= An) return;
    if(k == 0){
        An = min(An,sum);
        return;
    }
    if(a[k][k]){
        int p = a[k][n + 1];
        for(int i = k + 1;i <= n;i ++)
            if(a[k][i]) p ^= x[i];
        x[k] = p;
        if(x[k])    dfs(k - 1,sum + 1);
        else    dfs(k - 1,sum);
    }else{
        x[k] = 0;
        dfs(k - 1,sum);
        x[k] = 1;
        dfs(k - 1,sum + 1);
        x[k] = 0;
    }
}        
void solve(){
    for(int k = 1;k <= n;k ++){
        int f = 0;
        for(int i = k;i <= n;i ++)
            if(a[i][k]){
                for(int j = 1;j <= n + 1;j ++)  swap(a[i][j],a[k][j]);
                f = 1;
                break;
            }
        if(!f)  continue;
        for(int i = k + 1;i <= n;i ++)  if(a[i][k])
            for(int j = 1;j <= n + 1;j ++)  a[i][j] ^= a[k][j];
    }
    An = 1000000009;
    dfs(n,0);
    cout << An << endl;
}
int main(){
    while(scanf("%d",&n),n){
        int u,v;
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        for(int i = 1;i < n;i ++){
            scanf("%d%d",&u,&v);
            a[u][v] = a[v][u] = 1;
        }
        for(int i = 1;i <= n;i ++)  a[i][i] = a[i][n + 1] = 1;
        solve();
    }
    return 0;
}

题意：给定n个点，m个询问。每次询问一个矩形内有几个点。坐标范围10^7。

一眼看上去就很水啊。。坐标肯定是要离散化的。。询问跟着一起离散化。。然后以y为第一关键字，x为第二关键字排序。树状数组统计每个点左下角有多少个点。然后加加减减。。

离散化的细节貌似很恶心。。调着调着就A了。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char buf[20000000],*pt=buf,*o=buf;

inline int getint(){
    int s=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++;
    if(*pt=='-')f=-1,pt++; while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s*f;
}
inline void print(int x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}

struct point{
    int x,y,id;
    point(){
        id = -1;
    };
    point(int _x,int _y,int _id){
        x = _x, y = _y, id = _id;
    }
}p[2800010];

bool cmp(point a,point b){
    if(a.y == b.y){
        if(a.x == b.x)  return a.id < b.id;
        else    return a.x < b.x;
    }
    return a.y < b.y;
}

int n,m,N,P,pc = 0;
int X[810000],Y[810000],bx[810000],by[810000],bit[2800000],cnt[2800000];

void upd(int x){
    for(;x <= N;x += x & -x)    bit[x] ++;
}
int query(int x){
    int r = 0;
    for(;x;x -= x & -x) r += bit[x];
    return r;
}

int main(){
    fread(buf,1,20000000,stdin);
    n = getint(); m = getint();
    bx[0] = by[0] = 0;
    N = n + 1;
    P = (m << 2) + n;
    bx[N] = by[N] = 12345678;
    
    for(int i = 1;i <= n;i ++){
        X[i] = getint();
        Y[i] = getint();
        bx[i] = ++ X[i];  
        by[i] = ++ Y[i];
    }
    sort(bx + 1, bx + n + 1);
    sort(by + 1, by + n + 1);
    int cx = unique(bx , bx + n + 2) - bx -1;
    int cy = unique(by , by + n + 2) - by -1;
    for(int i = 1;i <= n;i ++){
        p[(m << 2) + i - 1].x = upper_bound(bx,bx + cx,X[i]) - bx;
        p[(m << 2) + i - 1].y = upper_bound(by,by + cy,Y[i]) - by;
    }
    int x1,y1,x2,y2,X1,X2,X3,Y1,Y2,Y3;
    for(int i = 1;i <= m;i ++){
        x1=  getint(); y1=getint();x2=getint();y2=getint();
        X1 = upper_bound(bx,bx + cx,x1) - bx;
        X2 = upper_bound(bx,bx + cx,x2) - bx;
        X3 = upper_bound(bx,bx + cx,x2 + 1) - bx;
        Y1 = upper_bound(by,by + cy,y1) - by;
        Y2 = upper_bound(by,by + cy,y2) - by;
        Y3 = upper_bound(by,by + cy,y2 + 1) - by;
        p[pc] = point(X3,Y3,pc ++);
        p[pc] = point(X1,Y3,pc ++);
        p[pc] = point(X3,Y1,pc ++);
        p[pc] = point(X1,Y1,pc ++);
    }
    
    sort(p,p + P,cmp);
    for(int i = 0;i < P;i ++){
        if(~ p[i].id)   cnt[p[i].id] = query(p[i].x);
        else    upd(p[i].x);
    }
    
    for(int i = 1;i <= m;i ++)
       print(cnt[i - 1 << 2] - cnt[(i - 1 << 2) + 1] - cnt[(i - 1 << 2) + 2] + cnt[(i - 1 << 2) + 3]),*o++='\n';
        
    return fwrite(buf,1,o-buf,stdout),0;
}

给定N和G。求Ans=G^(sigma(C(n,i)|i是n的约数))。Ans对999911659取模。

很高兴地发现它是质数。

其实求组合数的话。费马小定理乱搞除法取模。然后用lucas定理。很快就可以求出sigma(C(n,i)|i是n的约数)。

关键是求Ans的时候，这个指数太大了怎么破！

欢迎这个式子登场：a^b mod c=a^(b mod phi(c) + phi(c))。

注意到phi(质数)=质数-1。那么我们要模的就是999911658了。

可是lucas只对质数适用啊。

很高兴的分解质因数，发现999911658=2*3*4679*35617。

那么只需要模这4个数。然后用中国剩余定理合并。

这道题就被水了。一开始95分。发现指数里没有+phi(c)，导致指数是0，挂了一个点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=999911659ll,mod2=999911658ll;
ll ft[]={2,3,4679,35617},ft2[]={499955829,333303886,213702,28074};
ll p[4],q[4],n,g,m=0;
ll power(ll a,ll b,ll c){
    ll r=1; while(b){ if(b&1) r=r*a%c; b>>=1; a=a*a%c;}
    return r;
}ll calc(ll a,ll b,ll c){
    if(a<b) return 0; if(b>a-b) b=a-b; ll r=1,ca=1,cb=1;
    for(ll i=0;i<b;i++) ca=ca*(a-i)%c,cb=cb*(b-i)%c;
    return ca*power(cb,c-2,c)%c;
}ll lucas(ll a,ll b,ll c){
    ll r=1; while(a&&b&&r) r=r*calc(a%c,b%c,c)%c,a/=c,b/=c;
    return r;
}ll ext_gcd(ll a,ll b,ll&x,ll&y){
    if(!b){ x=1; y=0; return a;}
    ll xx,yy,d=ext_gcd(b,a%b,xx,yy);
    x=yy; y=xx-a/b*yy; return d;
}ll equ(ll a,ll b,ll c){
    ll x,y,d=ext_gcd(a,c,x,y); x*=b/d;
    while(x>=c/d) x-=c/d; while(x<0) x+=c/d;
    return x;
}ll solve(ll a,ll b){
    for(int i=0;i<4;i++) p[i]=lucas(a,b,ft[i]);
    for(int i=0;i<4;i++) q[i]=equ(ft2[i],1,ft[i]);
    ll r=0; for(int i=0;i<4;i++) r=(r+(p[i]*q[i]%mod2)*ft2[i]%mod2)%mod2;
    return r;
}int main(){
    cin>>n>>g;
    for(ll i=1;i*i<=n;i++) if(n%i==0){
        m=(m+solve(n,i))%mod2;
        if(i*i!=n) m=(m+solve(n,n/i))%mod2;
    }cout<<power(g,m+mod2,mod)<<endl;
    return 0;
}

判断连边的时候貌似有点麻烦、注意重合也算挡住。。。

另外如果用费用流替KM的话、不用添加一个点了、因为貌似不用每个点都流、

（其实我是来除草的、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxm=50000,inf=1061109567;
const ll mod=1000000007;
map<ll,int>id;  char str[30];   ll hash[100];
int h[100],p[maxm],c[maxm],cost[maxm],n1[maxm],q[maxm],sp[100],inq[100];
int D,n,S,T,TT,An=0,path[maxm],w[100][100],pre[100],tot=0,px[100],py[100];
inline void ae(int a,int b,int cc,int co){
    p[tot]=b; c[tot]=cc; cost[tot]=co;  n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; c[tot]=0;  cost[tot]=-co; n1[tot]=h[b]; h[b]=tot++;
}inline int spfa(){
    memset(sp,63,sizeof(sp));   memset(inq,0,sizeof(inq));
    int head=0,tail=1; sp[S]=0; q[0]=S; inq[S]=1; pre[S]=-1;
    while(head!=tail){
        int u=q[head++]; if(head>=maxm) head-=maxm; inq[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(c[i]>0&&sp[p[i]]>sp[u]+cost[i]){
                path[p[i]]=i, pre[p[i]]=u, sp[p[i]]=sp[u]+cost[i];
                if(!inq[p[i]]){ inq[p[i]]=1, q[tail++]=p[i]; if(tail>=maxm) tail-=maxm;}
            }
    }return sp[T]!=inf;
}inline int aug(){
    int delta=inf,  flow=0;
    for(int i=T;pre[i]!=-1;i=pre[i]) delta=min(delta,c[path[i]]);
    for(int i=T;pre[i]!=-1;i=pre[i]){
        c[path[i]]-=delta, c[path[i]^1]+=delta;
        flow+=cost[path[i]]*delta;
    }return flow;
}inline int cf(){
    int ret=0; while(spfa()) ret+=aug(); return ret;
}inline ll gethash(char *str){
    ll tmp=0; int len=strlen(str);
    for(int j=0;j<len;j++) if(str[j]>='A' && str[j]<='Z') str[j]=str[j]+32; 
    for(int j=0;j<len;j++){
        tmp=tmp*29+str[j];
        if(tmp>=mod) tmp%=mod;
    }return tmp;
}inline int ok(int u,int v){
    if((px[u]-px[v])*(px[u]-px[v])+(py[u]-py[v])*(py[u]-py[v])>D*D) return 0;
    for(int i=1;i<=n<<1;i++){
        if(i==u||i==v) continue;
        if((px[i]-px[u])*(px[i]-px[v])>0) continue;
        if((py[i]-py[u])*(py[i]-py[v])>0) continue;
        if((px[i]-px[u])*(py[v]-py[i])==(py[i]-py[u])*(px[v]-px[i])) return 0;
    }return 1;
}int main(){
    scanf("%d%d",&D,&n);
    S=0;TT=n<<1|1;T=TT+1;
    memset(h,0xff,sizeof(h));
    for(int i=1;i<=n;i++){
        scanf("%d%d%s",&px[i],&py[i],str);
        px[i]+=50;py[i]+=50;
        id[hash[i]=gethash(str)]=i;
        ae(S,i,1,0);
    }for(int i=1;i<=n;i++){
        scanf("%d%d%s",&px[n+i],&py[n+i],str);
        px[n+i]+=50;py[n+i]+=50;
        id[hash[n+i]=gethash(str)]=n+i;
        ae(n+i,T,1,0);
    }int u,v;
    for(int i=1;i<=n<<1;i++) for(int j=1;j<=n<<1;j++) w[i][j]=1;
    while(1){
        scanf("%s",str);    if(!strcmp("End",str)) break;   u=id[gethash(str)];
        scanf("%s",str);    v=id[gethash(str)];
        scanf("%d",&w[u][v]);   w[v][u]=w[u][v];
    }for(int i=1;i<=n;i++) for(int j=n+1;j<=n<<1;j++) if(ok(i,j)) ae(i,j,1,-w[i][j]);
    printf("%d\n",-cf()); return 0;
}

只是来除个草。。

这和当年CH上某cf赛制的题的B题很像。不过是这个的弱化版。

令f[i]表示第i个上面建仓库，1~i的都处理好了之后的最小花费。

那么f[i]=min{f[j]+w(j,i)}+c[i]

然后把w(j,i)化开：=p[j]*(x[i]-x[j])+p[j+1]*(x[i]-x[j+1])+...+p[i]*(x[i]-x[i])

=x[i]*p[j..i]-p[j]*x[j]+p[j+1]*x[j+1]+...+p[i]*x[i]

很明显前后两项都可以用前缀和数组O(1)出来。sp[i]=p[1..i],spx[i]=p[1]*x[1]+..+p[i]*x[i]

可惜这样还是n^2的。n还是100w这么凶残。

那么考虑斜率优化。

把w(j,i)带进去。

f[i]=min{f[j]+x[i](sp[i]-sp[j])-spx[i]+spx[j]}+c[i];

可以发现决策有单调性，x=sp[i]-sp[j],y=f[j]-spx[i]+spx[j],k=x[i]。那么就行了。O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double D;
const int maxn=1000005;
const double inf=1e30;
ll x[maxn],p[maxn],c[maxn],sp[maxn],spx[maxn],q[maxn],f[maxn];
inline D slope(int i,int j){
    ll dx=sp[i]-sp[j],dy=f[i]-f[j]+spx[i]-spx[j];
    if(!dx) return (dy>=0)?inf:-inf;
    return (D)dy/(D)dx;
}inline void read(ll &x){
    ll r=0,f=1;char ch;
    for(ch=getchar();(ch!='-')&&(ch<'0'||ch>'9');ch=getchar());
    if(ch=='-') f=-1; else r=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())r=r*10+ch-48;
    x=r*f;
}int main(){
    ll n;read(n);
    for(ll i=1;i<=n;i++){
        read(x[i]);read(p[i]);read(c[i]);
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }ll s=0,e=0;q[0]=0;
    for(ll i=1;i<=n;i++){
        while(s<e&&slope(q[s],q[s+1])<=(D)x[i])s++;
        f[i]=f[q[s]]+x[i]*(sp[i]-sp[q[s]])-(spx[i]-spx[q[s]])+c[i];
        while(s<e&&slope(q[e],q[e-1])>=slope(i,q[e]))e--;
        q[++e]=i;
    }printf("%lld\n",f[n]);
    return 0;
}

分类讨论大丈夫！！！WTF！！！

题意：

1.给你不等式ax>b

2.删除第i条插入的不等式

3.询问x=k时，满足多少个给定的不等式。

n的范围10w，k的绝对值范围是100w。

那么我们可以先解出这个不等式，把符合这个不等式的所有数所在的位置加一。

比如解出来x>1，就把2~100w全都加一。x<1，就把-100w~0全都加一。

那么明显就是修改区间，单点询问。可以用线段树很好的完成。

但是不知道为什么看到100w就后怕写线段树要玩常数。于是选择了树状数组。

用树状数组的话就需要差分。比如[l,r]都加一，那么在l的位置上加一，r+1的位置上减一。这个很基础。

负数的话下标怎么办呢？设置一个偏移量d=100w+1。修改第x个时，在第x+d个位置上修改。保证下标都是正的方便操作。

看来这道题已经没什么问题了。那我们去写写看？好的。

【以下为吐槽，看tips请跳过若干个自然段】

【四天前】树状数组两行秒。ax>b自以为是的除一除就算解好了。样例很快就过了。很自信的交上去。RE还是WA来着。。然后手忙脚乱改一改还是WA。。这个时候想到了对拍。网上搞了个标程拍一拍。。不拍不知道一拍吓一跳。。然后我就被拍扁重建了。（这是替罪羊树？

发现我解ax>b的方法很不科学。感觉都没考虑全。后来直接去玩double。结果精度萎出翔。。

然后我cave in了。。

【今天】上课的时候我重新想了想ax>b该怎么解。考虑a、b的正负，发现四种情况都列出来。四个if即可。最前面再特判一下a=0就没问题了。回来信心满满的写。

造了组大数据对拍过了。很高心。结果还是WA。真是要吐血。后来突然想到，万一它要删除已经删除掉的呢。那我不就挂了吗。于是我再开了个数组记录。这回，过了。。。。。

【吐槽完了】

几个tips：

1.a=0要特判

2.ax>b分四种情况讨论（我是这么做的保险，或者有更神的方法，可惜我不会

3.如果x解出来不在-100w~100w之间要特判

4.删除已经删除的不等式直接continue！！！

贴代码。本人放个r1的代码攒rp好了~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int d=1000001,n=2000001,r=1000000;
int bit[n+3],A[100005],B[100005],del[100005]={0};
char op,buf[5000000],*p=buf,*o=buf;
inline void upd(int x,int d){ for(;x<=n;x+=x&-x) bit[x]+=d;}
inline int qry(int x){ int s=0; for(;x;x-=x&-x) s+=bit[x]; return s;}
inline int getint(){ int s=0,f=1; while((*p!='-')&&(*p<'0'||*p>'9'))p++;
    if(*p=='-')f=-1,p++; while(*p>='0'&&*p<='9')s=s*10+*p++-48; return s*f;
}inline char getop(){
    while(*p!='Q'&&*p!='A'&&*p!='D')p++; return *p++;
}inline void print(int x){
    char str[30],*pt=str; if(!x)*o++=48;
    else{ while(x) *pt++=x%10+48,x/=10; while(pt--!=str)*o++=*pt;}
}int main(){
    fread(p,1,5000000,stdin);
    int q,a,b,k,i=0,t1,t2,An; q=getint();
    for(int qq=1;qq<=q;qq++){
        op=getop();
        if(op=='A'){
            a=getint(),t1=getint(),t2=getint(); b=t2-t1; ++i; A[i]=a; B[i]=b;
            if(a==0){ if(b<0)upd(1,1);}
            else if(b==0){
                if(a<0) upd(1,1),upd(d,-1); else upd(1+d,1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,1); else if(An<-r) upd(1,1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,1),upd(-An+d+1,-1);
                    else if(-An>r) upd(1,1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,1); else if(-An<-r) upd(1,1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,1),upd(An+d+1,-1);
                    else if(An>r) upd(1,1);
                }
            }
        }else if(op=='Q'){
            k=getint();
            print(qry(k+d));*o++='\n';
        }else{
            k=getint();
            if(del[k])continue;
            del[k]=1; a=A[k]; b=B[k];
            if(a==0){ if(b<0)upd(1,-1);}
            else if(b==0){
                if(a<0) upd(1,-1),upd(d,1); else upd(1+d,-1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,-1); else if(An<-r) upd(1,-1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,-1),upd(-An+d+1,1);
                    else if(-An>r) upd(1,-1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,-1); 
                    else if(-An<-r) upd(1,-1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,-1),upd(An+d+1,1);
                    else if(An>r) upd(1,-1);
                }
            }
        }
    }return fwrite(buf,1,o-buf,stdout),0;
}

以及这是我贡献的一片红色。

这么一来我也算一点搞过OI的人了。

这道题也是分层图。k次机会让边权变0。虽然以前搞过但是好久了我也忘了。于是写死写死地写。然后纠结了下标纠结了n久之后就过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=getint(),e=getint();
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    for(int k=1;k<=K;k++) for(int i=0;i<n;i++) for(int j=h[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]);
        ae(i+(k-1)*n,n*k+p[j],0);
    }dijkstra(s);
    printf("%d\n",d[n*K+e]);
    return 0;
}

n个顶点m条边。给你k次机会让边权减半。一次机会对一条边只能做一次。

n、k都是小于50，那么分层。然后就好了。有些细节比较纠结。于是调了好久。囧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int g[55][55]={0},hh[maxn],h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=1,e=n;
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    memcpy(hh,h,sizeof(h));
    for(int k=1;k<=K;k++) for(int i=1;i<=n;i++) for(int j=hh[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]); 
        ae(i+(k-1)*n,n*k+p[j],w[j]>>1);
    }dijkstra(s); int An=inf; for(int i=0;i<=K;i++) An=min(An,d[n*i+e]);
    printf("%d\n",An); return 0;
}

因为求的路径都是从在包含根的一条链上。所以可以考虑直接dfs。记录栈里元素的前缀和。

比如搜到u了，在set里面查询有没有d[u]-k，有的话就加一。然后继续往下dfs的时候把d[u]插入set。

别忘了最开始插个0。

10w个点递归会爆？最好写个手工栈？哈哈我会写了！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=200005;
int n,K,vis[maxn]={0},w[maxn],h[maxn],st[maxn],d[maxn],p[maxn],n1[maxn],tot=0;
set<int>S; char buf[5000000],*pt=buf;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); K=getint();
    memset(h,-1,sizeof(h)); S.clear(); S.insert(0);
    for(int i=1;i<=n;i++) w[i]=getint(); int u,v,An=0;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v);
    int top=0; st[++top]=1; S.insert(w[1]); d[1]=w[1]; vis[1]=1;
    while(top){
        int o=st[top],flag=0;
        for(int i=h[o];~i;i=n1[i]) if(!vis[p[i]]){
            st[++top]=p[i]; h[o]=n1[i]; d[p[i]]=d[o]+w[p[i]];
            vis[p[i]]=flag=1; S.insert(d[p[i]]);
            if(S.find(d[p[i]]-K)!=S.end()) An++;break;
        }if(!flag){ top--; S.erase(d[o]);}
    }printf("%d\n",An); return 0;
}