BZOJ3700: 发展城市
https://lydsy.com/JudgeOnline/problem.php?id=3700
分析:
- 枚举两个人，先求链交，求到两个端点的时间。
- 链交求法：求两两\(lca\)的\(4\)个点，去除掉不在路径上的，再去重，取\(dfs\)序最大的两个点。
- 同向，早进去的那个碗出来，异向，时间段有交。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
typedef long long ll;
typedef double f2;
int head[N],nxt[N<<1],to[N<<1],cnt,val[N<<1],n;
int m,qs[N],qt[N],bg[N],ed[N],et[N<<1],qc[N],dep[N];
int f[20][N<<1],Lg[N<<1],dis[N],dfn[N];
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
int x=0; char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(((x<<2)+x)<<1)+s-'0',s=nc();
return x;
}
int qv[N];
int ans;
inline void add(int u,int v,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
bool in_subtree(int x,int y) {
return dfn[y]>=dfn[x]&&dfn[y]<=ed[x];
}
int cmp(const int &x,const int &y) {return dep[x]<dep[y]?x:y;}
int lca(int x,int y) {
x=bg[x]; y=bg[y];
if(x>y) swap(x,y);int len=Lg[y-x+1];
return cmp(f[len][x],f[len][y-(1<<len)+1]);
}
void dfs(int x,int y) {
dfn[x]=++dfn[0];
dep[x]=dep[y]+1;
et[++et[0]]=x;
int i;
for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {
dis[to[i]]=dis[x]+val[i];
dfs(to[i],x); et[++et[0]]=x;
}
ed[x]=dfn[0];
}
int Dis(int x,int y) {return dis[x]+dis[y]-2*dis[lca(x,y)];}
inline bool cmp1(const int &x,const int &y) {return dfn[x]>dfn[y];}
int G[5];
void QuErY(int x,int y) {
G[1]=lca(qs[x],qs[y]);
G[2]=lca(qs[x],qt[y]);
G[3]=lca(qt[x],qs[y]);
G[4]=lca(qt[x],qt[y]);
int i;
for(i=1;i<=4;i++) if(!in_subtree(qc[x],G[i])||!in_subtree(qc[y],G[i])) G[i]=0;
sort(G+1,G+5,cmp1);
int ln=unique(G+1,G+5)-G-1;
for(i=1;i<=ln;i++) if(!G[i]) ln=i-1;
if(!ln) return ;
if(ln==1) {
int u=G[1];
ll d1=Dis(qs[x],u),d2=Dis(qs[y],u);
if(d1*qv[y]==d2*qv[x]) ans++;
return ;
}else {
int u=G[1],v=G[2];
ll d1=Dis(qs[x],u),d2=Dis(qs[x],v),d3=Dis(qs[y],u),d4=Dis(qs[y],v);
if(d1<=d2) {
if(d3<=d4) {
if((d1*qv[y] >= d3*qv[x] && d2*qv[y] <= d4*qv[x])||(d1*qv[y] <= d3*qv[x] && d2*qv[y] >= d4*qv[x])) ans++;
}else {
swap(d3,d4);
if((d2*qv[y]>=d3*qv[x]&&d1*qv[y]<=d4*qv[x])||(d4*qv[x]>=d1*qv[y]&&d3*qv[x]<=d2*qv[y])) ans++;
}
}else {
swap(d1,d2);
if(d3>d4) {
swap(d3,d4);
if((d1*qv[y] >= d3*qv[x] && d2*qv[y] <= d4*qv[x])||(d1*qv[y] <= d3*qv[x] && d2*qv[y] >= d4*qv[x])) ans++;
}else {
if((d2*qv[y]>=d3*qv[x]&&d1*qv[y]<=d4*qv[x])||(d4*qv[x]>=d1*qv[y]&&d3*qv[x]<=d2*qv[y])) ans++;
}
}
}
}
void clr() {
cnt=et[0]=0; dfn[0]=0; ans=0;
}
void solve() {
n=rd();
int i,x,y,z,j;
clr();
for(i=1;i<=n;i++) head[i]=0;
for(i=1;i<n;i++) {
x=rd(); y=rd(); z=rd();
add(x,y,z); add(y,x,z);
}
dfs(1,0);
for(i=et[0];i;i--) bg[et[i]]=i;
for(i=1;i<=et[0];i++) f[0][i]=et[i];
for(Lg[0]=-1,i=1;i<=et[0];i++) Lg[i]=Lg[i>>1]+1;
for(i=1;(1<<i)<=et[0];i++) {
for(j=1;j+(1<<i)-1<=et[0];j++) {
f[i][j]=cmp(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
}
dfn[0]=0;
m=rd();
for(i=1;i<=m;i++) qs[i]=rd(),qt[i]=rd(),qv[i]=rd(),qc[i]=lca(qs[i],qt[i]);
for(i=1;i<=m;i++) {
for(j=i+1;j<=m;j++) {
QuErY(i,j);
}
}
printf("%d\n",ans);
}
int main() {
int Tcas;
scanf("%d",&Tcas);
while(Tcas--) solve();
}