LOJ 6145 Easy (动态点分治+线段树)

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define N1 100005
  6 #define M1 505
  7 #define ll long long 
  8 #define uint unsigned int 
  9 #define ush unsigned short
 10 using namespace std;
 11 const int inf=0x3f3f3f3f;
 12 
 13 template <typename _T> void read(_T &ret)
 14 {
 15     ret=0; _T fh=1; char c=getchar();
 16     while(c<‘0‘||c>‘9‘){ if(c==‘-‘) fh=-1; c=getchar(); }
 17     while(c>=‘0‘&&c<=‘9‘){ ret=ret*10+c-‘0‘; c=getchar(); }
 18     ret=ret*fh;
 19 }
 20 
 21 struct Edge{
 22 int to[N1*2],nxt[N1*2],val[N1*2],head[N1],cte;
 23 void ae(int u,int v,int w)
 24 { cte++; to[cte]=v; nxt[cte]=head[u]; val[cte]=w; head[u]=cte; }
 25 }e;
 26 
 27 int lg[N1*2],de;
 28 namespace Tree{
 29 int dis[N1],dep[N1],fa[N1],st[N1],ff[N1*2][19],cur; //ord[N1*2],
 30 void dfs1(int x)
 31 {
 32     int j,v; st[x]=++cur; ff[cur][0]=x; 
 33     for(j=e.head[x];j;j=e.nxt[j])
 34     {
 35         v=e.to[j]; if(v==fa[x]) continue;
 36         fa[v]=x; dis[v]=dis[x]+e.val[j]; dep[v]=dep[x]+1;
 37         dfs1(v); ff[++cur][0]=x; 
 38     }
 39 }
 40 void init()
 41 {
 42     dep[1]=1; dfs1(1);
 43     int i,j;
 44     for(i=2,lg[1]=0;i<=cur;i++) lg[i]=lg[i>>1]+1;
 45     for(j=1;j<=lg[cur];j++)
 46     for(i=1;i+(1<<j)-1<=cur;i++)
 47         ff[i][j]=dep[ff[i][j-1]] < dep[ff[i+(1<<(j-1))][j-1]] ? ff[i][j-1] : ff[i+(1<<(j-1))][j-1];
 48 }
 49 inline int Dis(int x,int y)
 50 {
 51     int i=st[x],j=st[y],F; if(i>j) swap(i,j);
 52     F=dep[ff[i][lg[j-i+1]]] < dep[ff[j-(1<<lg[j-i+1])+1][lg[j-i+1]]] ? ff[i][lg[j-i+1]] : ff[j-(1<<lg[j-i+1])+1][lg[j-i+1]];
 53     return dis[x]+dis[y]-2*dis[F];
 54 }
 55 };
 56 
 57 struct SEG{
 58 struct node{ int ls,rs,mi; };
 59 node a[N1*230]; int root[N1],tot;
 60 inline void pushup(int rt)
 61 {
 62     a[rt].mi=inf;
 63     if(a[rt].ls) a[rt].mi=min(a[rt].mi,a[a[rt].ls].mi);
 64     if(a[rt].rs) a[rt].mi=min(a[rt].mi,a[a[rt].rs].mi);
 65 }
 66 void upd(int x,int l,int r,int &rt,int w)
 67 {
 68     if(!rt) rt=++tot;
 69     if(l==r){ a[rt].mi=w; return; }
 70     int mid=(l+r)>>1;
 71     if(x<=mid) upd(x,l,mid,a[rt].ls,w);
 72     else upd(x,mid+1,r,a[rt].rs,w);
 73     pushup(rt);
 74 }
 75 int qmi(int L,int R,int l,int r,int rt)
 76 {
 77     if(!rt) return inf;
 78     if(L<=l&&r<=R) return a[rt].mi;
 79     int mid=(l+r)>>1; int ans=inf;
 80     if(L<=mid) ans=min(ans,qmi(L,R,l,mid,a[rt].ls));
 81     if(R>mid) ans=min(ans,qmi(L,R,mid+1,r,a[rt].rs));
 82     return ans;
 83 }
 84 }s;
 85 
 86 using Tree::Dis;
 87 
 88 int n;
 89 int sz[N1],ms[N1],use[N1],pfa[N1],SZ,G;
 90 
 91 void gra(int x,int dad,int now)
 92 {
 93     int j,v; sz[x]=1; ms[x]=0; 
 94     if(now) s.upd(x,1,n,s.root[now],Dis(x,now));
 95     for(j=e.head[x];j;j=e.nxt[j])
 96     {
 97         v=e.to[j]; if(v==dad || use[v]) continue;
 98         gra(v,x,now);
 99         sz[x]+=sz[v]; ms[x]=max(ms[x],sz[v]);
100     }
101     ms[x]=max(ms[x],SZ-sz[x]);
102     if(ms[x]<ms[G]) G=x;
103 }
104 
105 void main_dfs(int x)
106 {
107     int j,v; use[x]=1;
108     s.upd(x,1,n,s.root[x],0);
109     for(j=e.head[x];j;j=e.nxt[j])
110     {
111         v=e.to[j]; if(use[v]) continue;
112         SZ=sz[v]; G=0; gra(v,x,x); pfa[G]=x; 
113         main_dfs(G);
114     }
115 }
116 
117 int main()
118 {
119     scanf("%d",&n);
120     int i,j,x,y,w,Q,q,l,r,D,ans;
121     for(i=1;i<n;i++) 
122     {    
123         read(x), read(y), read(w);
124         e.ae(x,y,w); e.ae(y,x,w);
125     }
126     Tree::init();
127     ms[0]=n; SZ=n; gra(1,0,0); main_dfs(G);
128     scanf("%d",&Q);
129     for(q=1;q<=Q;q++)
130     {
131         read(l), read(r), read(x); ans=inf;
132         for(y=x;y;y=pfa[y])
133         {
134             D=Dis(x,y);
135             ans=min(ans,D+s.qmi(l,r,1,n,s.root[y]));
136         }
137         printf("%d\r\n",ans);
138     }
139     return 0;
140 }