从loj上把#11#20都下了下来,windows 下能跑出来,请问为什么会RE呀?代码如下:
#include <bits/stdc++.h>
#define int long long
#define y1 y3
#define maxm 200005
#define maxn 1005
#define mod 1000000007
#define msk cerr
#define inf 0x3f3f3f3f3f3f3f
using namespace std;
int T,n,N,m,ans;
struct node{int to,nxt,w;}e[maxm<<1];
int h[maxm],star;
void link(int x,int y,int z){e[++star]=(node){y,h[x],z};h[x]=star;}
int dep[maxm],d[maxm],dfn[maxm],st[20][maxm],fa[20][maxm],dcnt,cnt;
void Dfs(int x,int fath,int z){
st[0][++dcnt]=fath;dfn[x]=dcnt;dep[x]=z;
fa[0][x]=fath;d[x]=d[fath]+1;
for(int i=1;i<=__lg(d[x]+1)+1;i++)fa[i][x]=fa[i-1][fa[i-1][x]];
for(int i=h[x];i;i=e[i].nxt){
int y=e[i].to,w=e[i].w;
if(y==fath)continue;
Dfs(y,x,z+w);
}
}
int CMP(int x,int y){return dfn[x]<dfn[y]?x:y;}
int LCA(int x,int y){
if(x==y)return x;
x=dfn[x];y=dfn[y];
if(x>y)swap(x,y);
int k=__lg(y-x++);
return CMP(st[k][x],st[k][y-(1<<k)+1]);
}
int dis(int x,int y){return (!x||!y)?0:dep[x]+dep[y]-2*dep[LCA(x,y)];}
struct ysn{
int i,x,w;
void init(){w=-inf;}
}Inf;
vector<ysn>add[maxm];
vector<int>adi[maxm],dei[maxm];
struct sgr{
ysn x,y;int w;
friend bool operator <(sgr x,sgr y){return x.w>y.w;}
void init(){x.init();y.init();w=-inf-inf;}
}tmp[6];
int calc(int x,int y,int w1,int w2){return dis(x,y)+w1+w2;}
int Find(int x,int k){for(int i=__lg(k+1)+1;i>=0;i--)if((1<<i)<=k)k-=1<<i,x=fa[i][x];return x;}
int MX;
sgr operator +(sgr x,sgr y){
int x1=x.x.x,x2=x.y.x,y1=y.x.x,y2=y.y.x;
int wx1=x.x.w,wx2=x.y.w,wy1=y.x.w,wy2=y.y.w;
int ix1=x.x.i,ix2=x.y.i,iy1=y.x.i,iy2=y.y.i;
sgr z=x;
tmp[1].init();tmp[2].init();tmp[3].init();tmp[4].init();tmp[5].init();
if(ix1!=iy1)tmp[1]={{ix1,x1,wx1},{iy1,y1,wy1},calc(x1,y1,wx1,wy1)};
if(ix1!=iy2)tmp[2]={{ix1,x1,wx1},{iy2,y2,wy2},calc(x1,y2,wx1,wy2)};
if(ix2!=iy1)tmp[3]={{ix2,x2,wx2},{iy1,y1,wy1},calc(x2,y1,wx2,wy1)};
if(ix2!=iy2)tmp[4]={{ix2,x2,wx2},{iy2,y2,wy2},calc(x2,y2,wx2,wy2)};
tmp[5]={{iy1,y1,wy1},{iy2,y2,wy2},calc(y1,y2,wy1,wy2)};
if(z.w<tmp[1].w)z=tmp[1];
if(z.w<tmp[2].w)z=tmp[2];
if(z.w<tmp[3].w)z=tmp[3];
if(z.w<tmp[4].w)z=tmp[4];
if(z.w<tmp[5].w)z=tmp[5];
return z;
}
int tot,ver[maxm];
struct Seg{
int l,r;
sgr mx;
}t[maxm*25];
#define ls t[k].l
#define rs t[k].r
void Pushup(int k){t[k].mx=t[ls].mx+t[rs].mx;}
sgr Add(sgr x,ysn y){
int x1=x.x.x,x2=x.y.x,y1=y.x;
int wx1=x.x.w,wx2=x.y.w,wy1=y.w;
int ix1=x.x.i,ix2=x.y.i,iy1=y.i;
sgr z=x;tmp[1].init();tmp[2].init();
if(ix1!=iy1)tmp[1]={{ix1,x1,wx1},{iy1,y1,wy1},calc(x1,y1,wx1,wy1)};
if(ix2!=iy1)tmp[2]={{ix2,x2,wx2},{iy1,y1,wy1},calc(x2,y1,wx2,wy1)};
MX=max({MX,tmp[1].w,tmp[2].w});
if(z.w<tmp[1].w)z=tmp[1];
if(z.w<tmp[2].w)z=tmp[2];
return z;
}
int X;
void Insert(int &k,int l,int r,int x,ysn y){
if(!k)k=++tot,t[k].l=t[k].r=0,t[k].mx.init();
t[k].mx=Add(t[k].mx,y);
// if(X==8)msk<<MX<<"\n";
if(l==r)return;
int mid=l+r>>1;
if(mid>=x)Insert(ls,l,mid,x,y);
else Insert(rs,mid+1,r,x,y);
}
void Del(int k,int l,int r,int x){
if(l==r)return t[k].mx.init();
int mid=l+r>>1;
if(mid>=x)Del(ls,l,mid,x);
else Del(rs,mid+1,r,x);
Pushup(k);
}
void Merge(int &x,int y,int l,int r){
if(!x||!y)return void(x+=y);
Add(t[x].mx,t[y].mx.x);Add(t[x].mx,t[y].mx.y);
if(l==r)return void(t[x].mx=t[x].mx+t[y].mx);
int mid=l+r>>1;
Merge(t[x].l,t[y].l,l,mid);
Merge(t[x].r,t[y].r,mid+1,r);
Pushup(x);
}
void pri(int k,int l,int r){
if(!k)return;
msk<<"["<<l<<","<<r<<"]:"<<t[k].mx.w<<" x:"<<t[k].mx.x.i<<" "<<t[k].mx.x.w<<" y:"<<t[k].mx.y.i<<" "<<t[k].mx.y.w<<"\n";
if(l==r)return;
int mid=l+r>>1;pri(ls,l,mid);pri(rs,mid+1,r);
}
void Sol(int x,int fath){
for(int i=h[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fath)continue;
Sol(y,x);
}
MX=-inf;
for(int i=h[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fath)continue;
Merge(ver[x],ver[y],1,N);
}
X=x;
// if(x==8)msk<<x<<" "<<tot<<" "<<MX<<"=========\n";
for(int i=0;i<add[x].size();i++){
int id=adi[x][i];ysn y=add[x][i];
Insert(ver[x],1,N,id,y);
// if(x==8)msk<<"ins "<<id<<":"<<y.i<<" "<<y.x<<" "<<y.w<<" "<<MX<<"\n";
}
// pri(ver[x],1,m);
// if(x==8)msk<<"ans:"<<MX-2*dep[x]<<"\n";
ans=max(ans,MX-2*dep[x]);
for(int i=0;i<dei[x].size();i++){
int id=dei[x][i];
// if(x==8) msk<<"del "<<id<<"\n";
Del(ver[x],1,N,id);
}
}
struct Q{int x,y,z;}q[maxm];
signed main(){
// freopen("20.in","r",stdin);
// freopen("wrong.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>T;Inf.init();int Min=-inf/5;t[0].mx.init();
while(T--){
star=dcnt=cnt=tot=0;ans=-inf;
for(int i=1;i<=2*max(n,m);i++)h[i]=ver[i]=0,
add[i].clear(),adi[i].clear(),dei[i].clear();
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;cin>>x>>y>>z;
link(x,y,z);link(y,x,z);
}
Dfs(1,0,0);
for(int j=1;j<=__lg(n+1)+1;j++)for(int i=1;i+(1<<j)-1<=n;i++)
st[j][i]=CMP(st[j-1][i],st[j-1][i+(1<<j-1)]);
// for(int i=1;i<=n;i++)msk<<i<<":"<<dep[i]<<"\n";
cin>>m;
for(int i=1;i<=m;i++)cin>>q[i].x>>q[i].y>>q[i].z;
for(int i=1;i<=m;i++){
int x=q[i].x,y=q[i].y,z=q[i].z;
if(x!=LCA(x,y)){
int w=dis(x,y)-2*z+dep[x];
add[x].push_back({i,y,w});
adi[x].push_back(i);
int di=d[x]-d[LCA(x,y)]-1,pa=Find(x,di);
dei[pa].push_back(i);
// msk<<i<<" "<<x<<" "<<y<<" "<<pa<<" "<<w<<"\n";
}
swap(x,y);
if(x!=LCA(x,y)){
int w=dis(x,y)-2*z+dep[x];
add[x].push_back({i,y,w});
adi[x].push_back(i+m);
int di=d[x]-d[LCA(x,y)]-1,pa=Find(x,di);
dei[pa].push_back(i+m);
// msk<<i<<" "<<x<<" "<<y<<" "<<pa<<" "<<w<<"\n";
}
}
N=m<<1;
Sol(1,0);
if(ans<=Min)cout<<"F\n";
else cout<<(ans>>1)<<"\n";
}
// while(1);
return 0;
}