3.27 模拟赛

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define db double
13 #define inf 21390621430000000LL
14 #define MAXN 100100
15 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
16 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
17 #define ren for(register int i=fst[x];i;i=nxt[i])
18 #define pb(i,x) vec[i].push_back(x)
19 #define pls(a,b) (a+b)%MOD
20 #define mns(a,b) (a-b+MOD)%MOD
21 #define mul(a,b) (1LL*(a)*(b))%MOD
22 using namespace std;
23 inline int read()
24 {
25     int x=0,f=1;char ch=getchar();
26     while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();}
27     while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();}
28     return x*f;
29 }
30 int n,nxt[MAXN<<1],fst[MAXN],to[MAXN<<1],cnt,val[MAXN<<1];
31 int sz[MAXN],mx[MAXN],Mx,Sum,Rt,vis[MAXN],dep[MAXN],fa[MAXN];
32 ll dis[MAXN][20];
33 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
34 void getrt(int x,int pa)
35 {
36     sz[x]=1,mx[x]=0;ren if(to[i]^pa&&!vis[to[i]])
37         {getrt(to[i],x);sz[x]+=sz[to[i]];mx[x]=max(mx[x],sz[to[i]]);}
38     mx[x]=max(mx[x],Sum-sz[x]);if(mx[x]<Mx) Mx=mx[x],Rt=x;
39 }
40 void Get(int x,int pa,int d){ren if(!vis[to[i]]&&to[i]^pa) dis[to[i]][d]=dis[x][d]+val[i],Get(to[i],x,d);}
41 void div(int x)
42 {
43     vis[x]=1;dis[x][dep[x]]=0;Get(x,0,dep[x]);
44     ren if(!vis[to[i]]) 
45         {Sum=sz[to[i]],Mx=n+2;getrt(to[i],0);dep[Rt]=dep[x]+1,fa[Rt]=x;div(Rt);}
46 }
47 ll mn[MAXN<<7];int ls[MAXN<<7],rs[MAXN<<7],rt[MAXN],tot;
48 void mdf(int &k,int l,int r,int x,ll w)
49 {
50     if(!k) k=++tot,mn[k]=inf;mn[k]=min(mn[k],w);if(l==r) return ;int mid=l+r>>1;
51     if(x<=mid) mdf(ls[k],l,mid,x,w);else mdf(rs[k],mid+1,r,x,w);
52 }
53 ll query(int k,int l,int r,int a,int b)
54 {
55     if(!k) return inf;if(l==a&&r==b) return mn[k];int mid=l+r>>1;
56     if(b<=mid) return query(ls[k],l,mid,a,b);
57     else if(a>mid) return query(rs[k],mid+1,r,a,b);
58     else return min(query(ls[k],l,mid,a,mid),query(rs[k],mid+1,r,mid+1,b));
59 }
60 void Mdf(int x){for(int anc=x;dep[anc];anc=fa[anc]) mdf(rt[anc],1,n,x,dis[x][dep[anc]]);}
61 ll Query(int x,int l,int r,ll res=inf)
62 {
63     for(int anc=x;dep[anc];anc=fa[anc]){res=min(res,dis[x][dep[anc]]+query(rt[anc],1,n,l,r));}
64     return res;
65 }
66 int main()
67 {
68     n=read();int a,b,c;rep(i,2,n) a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c);
69     Mx=n+2,Sum=n;getrt(1,0);dep[Rt]=1;div(Rt);rep(i,1,n) Mdf(i);
70     int T=read();while(T--) {a=read(),b=read(),c=read();printf("%lld\n",Query(c,a,b));}
71 }