題意：
給定一棵N<=100000個(gè)點(diǎn)的樹，
有Q<=100000個(gè)詢問，求(u,v)路徑上邊權(quán)最大值和最小值
做法：
動(dòng)態(tài)樹直接上了。。發(fā)覺在這里寫的題是越來越水..
注意要判空節(jié)點(diǎn)或者將空節(jié)點(diǎn)的最值賦為極限
1
#include <cstdio>
2#define min(a,b) ((a)<(b)?(a):(b))
3#define max(a,b) ((a)>(b)?(a):(b))
4#define n 100005
5struct Tsplay
6
{
7
#define Lch(x) T[x].l
8 #define Rch(x) T[x].r
9 #define Par(x) T[x].p
10 #define Max(x) T[x].max
11 #define Min(x) T[x].min
12 #define Val(x) T[x].val
13 #define Root(x) (Lch(Par(x))!=x&&Rch(Par(x))!=x)
14 int l,r,p;
15 int max,min,val;
16
} T[n];
17int vtx[200005],ne[200005],w[200005],L[n],q[n],tot;
18int N,Q;
19bool vis[100005];
20inline void Ins(int u,int v,int ww)
21{
22 vtx[++tot]=v;w[tot]=ww;ne[tot]=L[u];L[u]=tot;
23}
24inline void BuildTree()
25{
26 vis[q[1]=1]=1;
27 for (int h=1,t=1,u=q[h];h<=t;u=q[++h])
28 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
29 if (!vis[v])
30
{
31 Par(v)=u,Val(v)=w[p];
32 vis[q[++t]=v]=1;
33
}
34}
35inline void Tupdate(int x)
36{
37 Min(x)=Max(x)=Val(x);
38 if (Lch(x))
39 {
40 Min(x)=min(Min(x),Min(Lch(x)));
41 Max(x)=max(Max(x),Max(Lch(x)));
42 }
43 if (Rch(x))
44 {
45 Min(x)=min(Min(x),Min(Rch(x)));
46 Max(x)=max(Max(x),Max(Rch(x)));
47 }
48}
49inline void zig(int x)
50{
51 int y=Par(x),z=Par(y);
52 Lch(y)=Rch(x);
53 Par(Lch(y))=Rch(x)=y;
54 if (Lch(z)==y) Lch(z)=x;
55 else
56 if (Rch(z)==y) Rch(z)=x;
57 Par(x)=z,Par(y)=x;
58 Tupdate(y);
59}
60inline void zag(int x)
61{
62 int y=Par(x),z=Par(y);
63 Rch(y)=Lch(x);
64 Par(Rch(y))=Lch(x)=y;
65 if (Lch(z)==y) Lch(z)=x;
66 else
67 if (Rch(z)==y) Rch(z)=x;
68 Par(x)=z,Par(y)=x;
69 Tupdate(y);
70}
71inline void splay(int x)
72{
73 for (int y,z;!Root(x);)
74 {
75 y=Par(x),z=Par(y);
76 if (Root(y))
77 if (Lch(y)==x) zig(x);
78 else zag(x);
79 else
80 if (Lch(z)==y)
81 if (Lch(y)==x) zig(y),zig(x);
82 else zag(x),zig(x);
83 else
84 if (Rch(y)==x) zag(y),zag(x);
85 else zig(x),zag(x);
86 }
87 Tupdate(x);
88}
89inline void Expose(int x)
90{
91 for (int u=x,v=0;u;u=Par(u))
92 splay(u),Rch(u)=v,Tupdate(v=u);
93}
94inline void Query(int x,int y)
95{
96 Expose(x);
97 for (int u=y,v=0,vmax,vmin;u;u=Par(u))
98 {
99 if (splay(u),!Par(u))
100 {
101 vmax=-(1<<30),vmin=(1<<30);
102 if (v) vmin=min(vmin,Min(v)),vmax=max(vmax,Max(v));
103 if (Rch(u)) vmin=min(vmin,Min(Rch(u))),vmax=max(vmax,Max(Rch(u)));
104 printf("%d %d\n",vmin,vmax);
105 return;
106 }
107 Rch(u)=v,Tupdate(v=u);
108 }
109}
110int main()
111{
112 int x,y,w;
113 scanf("%d",&N);
114 for (int i=1;i<N;++i)
115 scanf("%d%d%d",&x,&y,&w),Ins(x,y,w),Ins(y,x,w);
116 BuildTree();
117 for (scanf("%d",&Q);Q--;)
118 {
119 scanf("%d%d",&x,&y);
120 Query(x,y);
121 }
122 return 0;
123}
124