SPOJ 375. QTREE 나무 사슬 분할

제목: 하나의 나무, a b c 는 a - b 변 의 가중치 가 c 를 대표 합 니 다.CHANGE x y  입력 한 x 조 변 의 가중치 를 y, QUERY x y 조회 x - y 경로 위의 가중치 의 최대 값 으로 변경 합 니 다.
 
처음으로 나무 사슬 의 분할 을 썼 는데 사실은 나무 사슬 의 분할 은 하나의 사상 이 라 고 할 수 밖 에 없다.나무 사슬 분할 바로 뿌리 노드 에서 잎 노드 까지 의 가장 긴 경로 의 가중치 가 선분 나무 에 대응 하 는 것 을 선택 한 다음 에 한 개의 나무의 뿌리 노드 에서 잎의 가장 긴 경로 의 가중치 가 선분 나무 에 대응 하 는 것 이다. 그러면 모든 점 을 처리 한 다음 에 선분 나무 구간 에서 가장 값 을 조회 하 는 것 이다.
구체 적 으로 이 블 로 그 를 볼 수 있다.http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html

  1 #include <cstdio>

  2 #include <cstdlib>

  3 #include <iostream>

  4 #include <cstring>

  5 #include <algorithm>

  6 using namespace std;

  7 typedef unsigned long long ull;

  8 typedef long long ll;

  9 const int inf = 0x3f3f3f3f;

 10 const double eps = 1e-8;

 11 const int maxn = 1e4+10;

 12 int top[maxn],fa[maxn],son[maxn],dep[maxn],siz[maxn],seg_tree[maxn<<2],head[maxn],pos[maxn];

 13 int edge,tot;

 14 struct

 15 {

 16     int to,next;

 17 }e[maxn<<1];

 18 void add(int x,int y)

 19 {

 20     e[edge].to = y;

 21     e[edge].next = head[x];

 22     head[x] = edge++;

 23 }

 24 

 25 void dfs(int r)

 26 {

 27     siz[r] = 1;

 28     son[r] = 0;

 29     for (int i = head[r]; i > 0; i = e[i].next)

 30         if (fa[r] != e[i].to)

 31         {

 32             dep[e[i].to] = dep[r] + 1;

 33             fa[e[i].to] = r;

 34             dfs(e[i].to);

 35             if (siz[e[i].to] > siz[son[r]])

 36                 son[r] = e[i].to;

 37             siz[r] += siz[e[i].to];

 38         }

 39 }

 40 

 41 void build(int r,int f)

 42 {

 43     pos[r] = tot++;

 44     top[r] = f;

 45     if (son[r] > 0)

 46         build(son[r],top[r]);

 47     for (int i = head[r]; i > 0; i = e[i].next)

 48     {

 49         if (fa[r] != e[i].to && son[r] != e[i].to)

 50             build(e[i].to,e[i].to);

 51     }

 52 }

 53 

 54 void update(int l,int r,int o,int x,int v)

 55 {

 56     if (l == r)

 57     {

 58         seg_tree[o] = v;

 59         return;

 60     }

 61     int mid = (l + r) >> 1;

 62     if (x <= mid)

 63         update(l,mid,o<<1,x,v);

 64     if (x > mid)

 65         update(mid+1,r,o<<1|1,x,v);

 66     seg_tree[o] = max(seg_tree[o<<1],seg_tree[o<<1|1]);

 67 }

 68 

 69 int query(int l,int r,int o,int ua,int ub)

 70 {

 71     if (ua <= l && ub >= r)

 72         return seg_tree[o];

 73     int mid = (l + r) >> 1;

 74     int t1,t2;

 75     t1 = t2 = 0;

 76     if (ua <= mid)

 77         t1 = query(l,mid,o<<1,ua,ub);

 78     if (ub > mid)

 79         t2 = query(mid+1,r,o<<1|1,ua,ub);

 80     return max(t1,t2);

 81 }

 82 

 83 int get_max(int ua,int ub)

 84 {

 85     int f1 = top[ua];

 86     int f2 = top[ub];

 87     int tmp = 0;

 88     while (f1 != f2)

 89     {

 90         if (dep[f1] < dep[f2])

 91             swap(f1,f2),swap(ua,ub);

 92         tmp = max(tmp,query(1,tot,1,pos[f1],pos[ua]));

 93         ua = fa[f1],f1 = top[ua];

 94     }

 95     if (ua == ub)

 96         return tmp;

 97     if (dep[ua] > dep[ub])

 98         swap(ua,ub);

 99     tmp = max(tmp,query(1,tot,1,pos[son[ua]],pos[ub]));

100     return tmp;

101 }

102 

103 int d[maxn][3];

104 void init()

105 {

106     int n;

107     scanf ("%d",&n);

108     memset(dep,0,sizeof(dep));

109     memset(son,0,sizeof(son));

110     memset(head,0,sizeof(head));

111     memset(fa,0,sizeof(fa));

112     memset(top,0,sizeof(top));

113     int root = (n+1)>>1;

114     fa[root] = dep[root] =0;

115     tot = edge = 1;

116     int a,b,c;

117     for (int i = 1; i < n; i++)

118     {

119         scanf ("%d%d%d",&a,&b,&c);

120         add(a,b),add(b,a);

121         d[i][0] = a,d[i][1] = b,d[i][2] = c;

122     }

123     dfs(root);

124     build(root,root);

125     tot--;

126     for (int i = 1; i < n; i++)

127     {

128         if (dep[d[i][0]] < dep[d[i][1]])

129             swap(d[i][1],d[i][0]);

130         update(1,tot,1,pos[d[i][0]],d[i][2]);

131     }

132 

133 }

134 int main(void)

135 {

136     #ifndef ONLINE_JUDGE

137         freopen("in.txt","r",stdin);

138     #endif // ONLINE_JUDGE

139     int t;

140     scanf ("%d",&t);

141     while (t--)

142     {

143          init();

144          char op[10];

145          while (scanf ("%s",op),op[0] != 'D')

146          {

147              int x,y;

148              scanf ("%d%d",&x,&y);

149              if (op[0] == 'C')

150                 update(1,tot,1,pos[d[x][0]],y);

151             if (op[0] == 'Q')

152                 printf("%d
",get_max(x,y));

153          }

154     }

155     return 0;

156 }