差分约束/并查集/BFS均可。
  这道题的弱化版可参见BZOJ1202

#include bits/stdc++.h using namespace std;const int Max=100010;int n,m,size,tag,head,tail=1;int first[Max],dis[Max],q[Max 3],sum[Max],v[Max];struct shu{int to,next,len;}e[Max 3];inline int get_int() int x=0,f=1;char c; for(c=getchar();(!isdigit(c)) (c!=\'-\');c=getchar()); if(c==\'-\') f=-1,c=getchar(); for(;isdigit(c);c=getchar()) x=(x 3)+(x 1)+c-\'0\'; return x*f;inline void build(int x,int y,int z){e[++size].next=first[x],first[x]=size,e[size].to=y,e[size].len=z;}inline void init() n=get_int(),m=get_int(); for(int i=1;i =m;i++) int x=get_int(),y=get_int(),z=get_int(); build(y,x,-z),build(x,y,z); for(int i=1;i =n;i++) build(0,i,0);inline bool SPFA() memset(dis,0x3f,sizeof(dis)); q[1]=0,dis[0]=0; while(head tail) int p=q[++head];v[p]=0; for(int u=first[p];u;u=e[u].next) int to=e[u].to; if(dis[to] dis[p]+e[u].len) dis[to]=dis[p]+e[u].len; if(!v[to]) sum[to]=sum[p]+1; if(sum[to] n) return 1; q[++tail]=to,v[to]=1; return 0;inline void solve() if(SPFA()) puts( impossible ); else int l=1e9,r=-1e9; for(int i=1;i =n;i++) l=min(l,dis[i]),r=max(r,dis[i]); cout r-l \\n ;int main() init(); solve(); return 0;

  最短路计数。
  现在才知道最短路计数怎么写。。。
  具体来说就是每次更新时分两种情况判断：
  1.dis[to] dis[p]+e[u].lendis[to] dis[p]+e[u].lendis[to] dis[p]+e[u].len
  说明当前不是最短路，所以f[to]f[to]f[to]重新变为000。
  2.dis[to]=dis[p]+e[u].lendis[to]=dis[p]+e[u].lendis[to]=dis[p]+e[u].len
  说明目前是最短路，所以f[to]+=f[p]f[to]+=f[p]f[to]+=f[p]。
  那么对于这道题，计算完最短路个数后枚举中间点和中间边即可，注意去重。

#include bits/stdc++.h using namespace std;const int mod=1e9+7;const int Max=100010;int n,m,s,t,size,tot;long long ans;int first[Max],cntS[Max],cntT[Max],v[Max];long long disS[Max],disT[Max];struct shu{int to,next,len;}e[Max 2];inline int get_int() int x=0,f=1;char c; for(c=getchar();(!isdigit(c)) (c!=\'-\');c=getchar()); if(c==\'-\') f=-1,c=getchar(); for(;isdigit(c);c=getchar()) x=(x 3)+(x 1)+c-\'0\'; return x*f;inline void build(int x,int y,int z) e[++size].next=first[x],first[x]=size,e[size].to=y,e[size].len=z; e[++size].next=first[y],first[y]=size,e[size].to=x,e[size].len=z;inline void dijkstra(long long *const dis,int *const cnt,int s,int t) for(int i=1;i =n;i++) dis[i]=1e9,v[i]=0; priority_queue pair int,int q; dis[s]=0,q.push(make_pair(0,s)),cnt[s]=1; while(q.size()) int p=q.top().second;q.pop(); if(v[p]) continue;v[p]=1; for(int u=first[p];u;u=e[u].next) int to=e[u].to; if(dis[to] dis[p]+e[u].len) cnt[to]=0,dis[to]=dis[p]+e[u].len; q.push(make_pair(-dis[to],to)); if(dis[to]==dis[p]+e[u].len) cnt[to]=(cnt[to]+cnt[p])%mod;inline void solve(int p) if(disS[p]+disT[p]!=tot) return; if(disS[p]==disT[p]) ans=(ans-1ll*cntS[p]*cntS[p]%mod*cntT[p]%mod*cntT[p]%mod+mod)%mod; if(disS[p]*2 =tot) return; for(int u=first[p];u;u=e[u].next) int to=e[u].to; if(disS[p]+disT[to]+e[u].len!=tot||disT[to]*2 =tot) continue; ans=(ans-1ll*cntS[p]*cntS[p]%mod*cntT[to]%mod*cntT[to]%mod+mod)%mod;signed main() n=get_int(),m=get_int(),s=get_int(),t=get_int(); for(int i=1;i =m;i++) int x=get_int(),y=get_int(),z=get_int(); build(x,y,z); dijkstra(disS,cntS,s,t),dijkstra(disT,cntT,t,s),tot=disS[t],ans=1ll*cntS[t]*cntS[t]%mod; for(int i=1;i =n;i++) solve(i); cout (ans%mod+mod)%mod; return 0;

  DFSDFSDFS序，树状数组。
  首先明确一点，如果两个路径有交，那么其中一条路径的LCALCALCA必定在另一条路径上（如果你举出了反例那么你会发现不是树形结构，因为会出现有一个点有两个父节点的情况）。
  那么对于新加进来的路径，计算前面的路径有多少与其有交集，分三种情况进行讨论：

  如图，s−ts-ts−t为新加进来的边，其余为之前加进的边。
  1.s1,t2s1,t2s1,t2
  这种路径就在加入的时候分别在s1,s2s1,s2s1,s2加111，在lcalcalca减222。查询时计算以lca(s,t)lca(s,t)lca(s,t)为根的子树和即可。
  2.s2,t2s2,t2s2,t2
  这种路径就在加入的时候在lca(s2,t2)lca(s2,t2)lca(s2,t2)处加111就行了，查询时计算sum[s]+sum[t]−2∗sum[lca]sum[s]+sum[t]-2*sum[lca]sum[s]+sum[t]−2∗sum[lca]就行了。
  3.s3,t3s3,t3s3,t3
  单独记录一个数组算就行了。单独算的原因时因为前面两种做法都会算到它。

#include bits/stdc++.h using namespace std;const int Max=1000010;int n,m,s,tot,f;long long ans;int s1[Max],s2[Max],first[Max],num[Max],l[Max],r[Max];int size[Max],top[Max],son[Max],fa[Max],dep[Max];struct shu{int to,next;}e[Max 1];inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2 (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;inline int get_int(){ char ch=nc();int sum=0; while(!(ch =\'0\' ch =\'9\'))ch=nc(); while(ch =\'0\' ch =\'9\')sum=sum*10+ch-48,ch=nc(); return sum;inline void build(int x,int y) e[++s].next=first[x],first[x]=s,e[s].to=y; e[++s].next=first[y],first[y]=s,e[s].to=x;void dfs1(int p) size[p]=1,l[p]=++tot; for(int u=first[p];u;u=e[u].next) int to=e[u].to; if(to==fa[p]) continue; fa[to]=p,dep[to]=dep[p]+1,dfs1(to),size[p]+=size[to]; if(size[to] size[son[p]]) son[p]=to; r[p]=tot;void dfs2(int p,int tp) top[p]=tp; if(!son[p]) return; dfs2(son[p],tp); for(int u=first[p];u;u=e[u].next) int to=e[u].to; if(to==fa[p]||to==son[p]) continue; dfs2(to,to);inline int LCA(int x,int y) while(top[x]^top[y]) if(dep[top[x]] dep[top[y]]) swap(x,y); x=fa[top[x]]; return dep[x] dep[y]?x:y;inline void add(int *s,int pos,int x){if(!pos)return;for(int i=pos;i =n;i+=i (-i)) s[i]+=x;}inline int Q(int *s,int pos) int sum=0; for(int i=pos;i;i-=i (-i)) sum+=s[i]; return sum;inline void calc(int x,int y) f=LCA(x,y); ans+=Q(s1,l[x])+Q(s1,l[y])-2*Q(s1,l[f])+Q(s2,r[f])-Q(s2,l[f]-1)+num[f];inline void modify(int x,int y) ++num[f],add(s1,l[f],1),add(s1,r[f]+1,-1); add(s2,l[x],1),add(s2,l[y],1),add(s2,l[f],-2);inline void init() n=get_int(),m=get_int(); for(int i=1;i n;i++) int x=get_int(),y=get_int(); build(x,y); dfs1(1),dfs2(1,1);inline void solve() while(m--) int x=get_int(),y=get_int(); calc(x,y); modify(x,y); cout ans;int main() int size=40 20; __asm__ ( movq %0,%%rsp\\n :: r ((char*)malloc(size)+size));//提交用这个  init(); solve(); exit(0);