应该是有图不连通，然后有询问在不同的联通子图上吧
by NaCly_Fish @ 2019-01-05 08:36:17
@[NaCly_Fish](/space/show?uid=115864) 忽视掉这条，我sb，看错题了
by NaCly_Fish @ 2019-01-05 08:36:51
@[lzx729687719](/space/show?uid=60895) 感觉第13个点数据有问题，我跑这个点1700ms。。。。。。
by King_of_gamers @ 2019-01-05 09:37:28
但我是wa啊
开了O2变RE...
Loj数据测貌似是爆栈了
但是我写的就是常规树剖啊...
by 温栀槿 @ 2019-01-05 09:46:08
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l+r)>>1)
#define lson num<<1,l,mid
#define rson num<<1|1,mid+1,r
#define lowbit(x) x&-x
const int N=5e5+1e3;
int mx[N],head[N],cnt,s[N<<2],ly[N<<2],id[N],idx,siz[N],son[N],fa[N],w[N],top[N],a[N],dep[N],cl[N],cr[N],sp[N],n,m,pp[N];
int sl,sr,sw;
struct ii{
int to,next,w,fr;
}e[N*2];
bool cmp(int a,int b){
return cl[a]<cl[b];
}
inline void add(int u,int v,int w){
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].fr=u;
e[cnt].next=head[u];
head[u]=cnt;
}
inline int sa(int num,int l,int r,int x,int y){
if(x<=l&&r<=y) {
return s[num];
}
int sum=0;
if(x<=mid) sum+=sa(lson,x,y);
if(y>mid) sum+=sa(rson,x,y);
return sum;
}
inline void pushdown(int num,int l,int r){
if(!ly[num]||l==r) return ;
mx[num<<1]=max(mx[num<<1],ly[num]);
ly[num<<1]=max(ly[num<<1],ly[num]);
mx[num<<1|1]=max(mx[num<<1|1],ly[num]);
ly[num<<1|1]=max(ly[num<<1|1],ly[num]);
ly[num]=0;
}
inline void upd(int num,int l,int r,int x,int y,int k){
if (x > y || y<l || x>r) return;
if(x<=l&&r<=y){
mx[num]=max(mx[num],k);
ly[num]=max(ly[num],k);
return;
}
pushdown(num,l,r);
if(x<=mid) upd(lson,x,y,k);
if(y>mid) upd(rson,x,y,k);
mx[num]=max(mx[num<<1],mx[num<<1|1]);
}
inline void build(int num,int l,int r){
if(l==r){
s[num]=w[l];
return ;
}
build(lson);
build(rson);
s[num]=s[num<<1]+s[num<<1|1];
}
inline int sam(int l, int r) {
return sa(1,1,n,l,r);
}
inline int mmx(int num,int l,int r,int x,int y){
pushdown(num,l,r);
if(l==x&&r==y){
return mx[num];
}
int mxs=0;
if(x<=mid) mxs=max(mxs,mmx(lson,x,y));
if(y>mid) mxs=max(mxs,mmx(rson,x,y));
return mxs;
}
inline void dfs1(int s,int f,int d){
dep[s]=d;
siz[s]=1;
fa[s]=f;
for(int i=head[s];~i;i=e[i].next){
int v=e[i].to;
if(v==f) continue;
dfs1(v,s,d+1);
siz[s]+=siz[v];
if(siz[v]>siz[son[s]]) son[s]=v;
}
}
inline void dfs2(int s,int tp){
top[s]=tp;
id[s]=++idx;
w[idx]=a[s];
if(!son[s]) return ;
dfs2(son[s],tp);
for(int i=head[s];~i;i=e[i].next){
int v=e[i].to;
if(v==fa[s]||v==son[s]) continue;
dfs2(v,v);
}
}
inline int sfam(int x,int y){
int tx = top[x], ty = top[y], ans = 0;
while (tx != ty)
{
if (dep[tx] >= dep[ty]) ans += sam(id[tx], id[x]), x = fa[tx], tx = top[x];
else ans += sam(id[ty], id[y]), y = fa[ty], ty = top[y];
}
if (id[x] <= id[y]) ans += sam(id[x] + 1, id[y]);
else ans += sam(id[y] + 1, id[x]);
return ans;
}
inline void wk1(int x,int y,int k){
int t1=clock();
int num=0;
int len=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
cl[++num]=id[top[x]];
cr[num]=id[x];
sp[num]=num;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
cl[++num]=id[x]+1;
cr[num]=id[y];
sp[num]=num;
sort(sp+1,sp+1+num,cmp);
if(cl[sp[1]]>1) upd(1,1,n,1,cl[sp[1]]-1,k);
if(cr[sp[num]]<n) upd(1,1,n,cr[sp[num]]+1,n,k);
for(int i=1;i<num;i++) upd(1,1,n,cr[sp[i]]+1,cl[sp[i+1]]-1,k);
return;
}
inline ll get_ans(int x,int y){
ll ans=9223372036854775807;
if(x==y) return 0;
while(dep[x]!=dep[y]){
if(dep[x]<dep[y]) swap(x,y);
ans=min(ans,(ll)max(sw-w[id[x]],mmx(1,1,n,id[x],id[x])));
x=fa[x];
}
while(x!=y){
if(dep[x]<dep[y]) swap(x,y);
ans=min(ans,(ll)max(sw-w[id[x]],mmx(1,1,n,id[x],id[x])));
x=fa[x];
}
return ans;
}
template<class T>
inline void read(T &num){
T x=0,f=1;char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
num=f*x;
}
int main(){
memset(head,-1,sizeof(head));
read(n),read(m);
for(int i=1;i<n;i++){
int p,q,w;
read(p),read(q),read(w);
add(p,q,w);
add(q,p,w);
}
dfs1(1,0,1);
for(int i=1;i<=cnt;i+=2){
if(dep[e[i].to]>dep[e[i].fr]) a[e[i].to]=e[i].w;
else a[e[i].fr]=e[i].w;
}
dfs2(1,1);
build(1,1,n);
for(int i=1;i<=m;i++){
int p,q;
read(p),read(q);
int mt=sfam(p,q);
wk1(p,q,mt);
if(mt>=sw){
sl=p;
sr=q;
sw=mt;
}
}
printf("%lld\n",get_ans(sl,sr));
return 0;
}
```
by 温栀槿 @ 2019-01-05 09:47:08
就dfs1爆了好像
其他别看太长了
by 温栀槿 @ 2019-01-05 09:47:31
@[温栀槿](/user/60895) 爆栈了
by sleepyNick @ 2019-11-10 12:19:08