树链剖分 模板题
1 #include<iostream>
2 #include<cstring>
3 #include<cmath>
4 #include<cstdio>
5 using namespace std;
6 #define MAXN 10010
7 #define INF 987654321
8 struct tree_node
9 {
10 int left,right;
11 int num;
12 };
13 struct node
14 {
15 int r,id;
16 node *next;
17 };
18 node *graph[MAXN];
19 node memo[MAXN*2];
20 tree_node tree[4*MAXN];
21 int d[MAXN],father[MAXN],line[MAXN],son[MAXN],sonl[MAXN],top[MAXN],mark[MAXN],home[MAXN];
22 int n,m,edge[MAXN];
23 int etop;
24 void add(int x,int y,int id)
25 {
26 node *p=&memo[etop++];
27 p->r=y; p->id=id; p->next=graph[x]; graph[x]=p;
28 p=&memo[etop++];
29 p->r=x; p->id=id; p->next=graph[y]; graph[y]=p;
30 }
31 int dfs1(int i,int deep,int fa,int edge_id)
32 {
33 d[i]=deep; father[i]=fa; line[i]=edge_id;
34 int size=1,maxsize=0,temp;
35 for(node *p=graph[i];p;p=p->next)
36 if(p->r!=father[i])
37 {
38 temp=dfs1(p->r,deep+1,i,p->id);
39 if(temp>maxsize)
40 {
41 maxsize=temp; son[i]=p->r; sonl[i]=p->id;
42 }
43 size+=temp;
44 }
45 return size;
46 }
47 void dfs2(int x,int y)
48 {
49 mark[line[x]]=++m; top[x]=y;
50 home[m]=line[x];
51 if(son[x]==-1) return ;
52 dfs2(son[x],y);
53 for(node *p=graph[x];p;p=p->next)
54 if(p->r!=father[x]&&p->r!=son[x]) dfs2(p->r,p->r);
55 }
56 int build_tree(int t)
57 {
58 if(tree[t].left==tree[t].right)
59 {
60 return tree[t].num=edge[home[tree[t].left]];
61 }
62 int mid=(tree[t].left+tree[t].right)/2;
63 tree[2*t].left=tree[t].left; tree[2*t].right=mid;
64 tree[2*t+1].left=mid+1; tree[2*t+1].right=tree[t].right;
65 return tree[t].num=max(build_tree(2*t),build_tree(2*t+1));
66 }
67 void change(int i,int pos,int x)
68 {
69 if(tree[i].left==tree[i].right)
70 {
71 tree[i].num=x;
72 return ;
73 }
74 int mid=(tree[i].left+tree[i].right)/2;
75 if(pos<=mid) change(2*i,pos,x);
76 else change(2*i+1,pos,x);
77 tree[i].num=max(tree[i*2].num,tree[i*2+1].num);
78 }
79 int search(int i,int x,int y)
80 {
81 if(tree[i].left==x&&tree[i].right==y)
82 return tree[i].num;
83 int mid=(tree[i].left+tree[i].right)/2;
84 if(y<=mid) return search(2*i,x,y);
85 else if(x>mid) return search(2*i+1,x,y);
86 else return max(search(2*i,x,mid),search(2*i+1,mid+1,y));
87 }
88
89
90 void build()
91 {
92 dfs1(1,1,-1,0);
93 dfs2(1,1);
94 tree[1].left=1; tree[1].right=n;
95 build_tree(1);
96 }
97 void solve()
98 {
99 char c[10];
100 int x,y,nx,ny,ans;
101 while(1)
102 {
103 scanf("%s",c);
104 if(c[0]=='D') break;
105 scanf("%d%d",&x,&y);
106 if(c[0]=='C') change(1,mark[x],y);
107 if(c[0]=='Q')
108 {
109 if(x==y)
110 {
111 printf("0\n"); continue;
112 }
113 for(ans=-INF;top[x]!=top[y];x=father[nx])
114 {
115 nx=top[x]; ny=top[y];
116 if(d[nx]<d[ny])
117 {
118 swap(x,y); swap(nx,ny);
119 }
120 ans=max(ans,search(1,mark[line[nx]],mark[line[x]]));
121 }
122 if(d[x]<d[y]) swap(x,y);
123 if(x!=y)
124 ans=max(ans,search(1,mark[sonl[y]],mark[line[x]]));
125 printf("%d\n",ans);
126 }
127 }
128 }
129
130
131 int main()
132 {
133 int T;
134 scanf("%d",&T);
135 while(T--)
136 {
137 etop=m=0; edge[0]=-INF;
138 memset(son,0xff,sizeof(son));
139 memset(sonl,0xff,sizeof(sonl));
140 memset(graph,0,sizeof(graph));
141 int x,y;
142 int i;
143 scanf("%d",&n);
144 for(i=1;i<n;i++)
145 {
146 scanf("%d%d%d",&x,&y,edge+i);
147 add(x,y,i);
148 }
149 build();
150 solve();
151 }
152 return 0;
153 }