51 nod 1766 树上的最远点对(线段树+lca)-白红宇

51 nod 1766 树上的最远点对(线段树+lca)

阅读量：6209 次

发布时间：2019-06-21

本文共 3345 字，大约阅读时间需要 11 分钟。

1766 树上的最远点对

基准时间限制：3 秒空间限制：524288 KB 分值: 80

n个点被n-1条边连接成了一颗树，给出a~b和c~d两个区间，表示点的标号请你求出两个区间内各选一点之间的最大距离，即你需要求出max｛dis(i,j) |a<=i<=b,c<=j<=d｝

（PS 建议使用读入优化）

Input

第一行一个数字 n n<=100000。第二行到第n行每行三个数字描述路的情况， x,y,z (1<=x,y<=n,1<=z<=10000)表示x和y之间有一条长度为z的路。第n+1行一个数字m，表示询问次数 m<=100000。接下来m行，每行四个数a,b,c,d。

Output

共m行，表示每次询问的最远距离

Input示例

51 2 12 3 21 4 34 5 412 3 4 5

Output示例

/*51 nod 1766 树上的最远点对(线段树+lca)problem:n个点被n-1条边连接成了一颗树，给出a~b和c~d两个区间，表示点的标号请你求出两个区间内各选一点之间的最大距离，即你需要求出max｛dis(i,j) |a<=i<=b,c<=j<=d｝solve:最开始想的是树链剖分,结果发现是区间[a,b]. 看成链了...看题解说的是最远点有合并的性质.  就是[a,b]的最远点ta,tb和[b+1,c]的最远点tc,td这四个点中距离最远的就是[a,c]的最远点..  证明并没有怎么看懂- -如果用线段树和并的话，需要快速求两点之间的距离.  可以用st快速求lca来解决,预处理便能得到O(1)的.然后就是线段树合并时处理下.http://blog.csdn.net/rzo_kqp_orz/article/details/52280811hhh-2016/09/15-21:16:26*/#pragma comment(linker,"/STACK:124000000,124000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define lson i<<1#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define scanfi(a) scanf("%d",&a)#define scanfs(a) scanf("%s",a)#define scanfl(a) scanf("%I64d",&a)#define scanfd(a) scanf("%lf",&a)#define key_val ch[ch[root][1]][0]#define eps 1e-7#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const ll mod = 1e9+7;const int MAXN = 100010;const double PI = acos(-1.0);template
               
                 void read(T&num){ char CH; bool F=false; for(CH=getchar(); CH<'0'||CH>'9'; F= CH=='-',CH=getchar()); for(num=0; CH>='0'&&CH<='9'; num=num*10+CH-'0',CH=getchar()); F && (num=-num);}int stk[70], tp;template
                
                  inline void print(T p){ if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + '0'); putchar('\n');}int rmq[2*MAXN];struct ST{ int mm[2*MAXN]; int dp[2*MAXN][20]; void init(int n) { mm[0] = -1; for(int i = 1; i <= n; i++) { mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1]; dp[i][0] = i; } for(int j = 1; j <= mm[n]; j++) for(int i = 1; i + (1<
                 
                  < rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1]; } int query(int a,int b) { if(a > b)swap(a,b); int k = mm[b-a+1]; return rmq[dp[a][k]] <= rmq[dp[b-(1<
                  
                   <
                   
                    > 1; build(lson,l,mid); build(rson,mid+1,r); push_up(i);}int from,to;void solve(int a,int b,ll &len){ if(distan(a,b) > len) { len = distan(a,b); from = a,to = b; }}void query(int i,int l,int r,int &ta,int &tb){ ta = tb = -1; if(tree[i].l >= l && tree[i].r <= r) { ta = tree[i].s ; tb = tree[i].t; return ; } int mid = (tree[i].l + tree[i].r) >> 1; int ls,lt,rs,rt; ls = lt = rs = rt= -1; if(r <= mid) query(lson,l,r,ta,tb); else if(l > mid) query(rson,l,r,ta,tb); else { ll tans = -1; query(lson,l,mid,ls,lt); query(rson,mid+1,r,rs,rt); solve(ls,rt,tans); solve(ls,rs,tans); solve(lt,rt,tans); solve(lt,rs,tans); solve(ls,lt,tans); solve(rs,rt,tans); ta = from ,tb = to; } push_up(i);}int main(){// freopen("in.txt","r",stdin); int n; int u,v,w; read(n); ini(); for(int i = 1; i < n; i++) { read(u),read(v),read(w); add_edge(u,v,w); add_edge(v,u,w); } dis[1] = 0; LCA_init(1,n); build(1,1,n); int a,b,m; int max1,min1,max2,min2; read(m); for(int i = 1; i <= m; i++) { ll ans = 0; read(u),read(v); read(a),read(b); query(1,u,v,max1,min1); query(1,a,b,max2,min2);// cout << max1 << max2 << min1<
                    
                     <