首页 > 代码库 > spoj375 QTREE - Query on a tree
spoj375 QTREE - Query on a tree
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.
We will ask you to perfrom some instructions of the following form:
- CHANGE i ti : change the cost of the i-th edge to ti
or - QUERY a b : ask for the maximum edge cost on the path from node a to node b
Input
The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.
For each test case:
- In the first line there is an integer N (N <= 10000),
- In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
- The next lines contain instructions "CHANGE i ti" or "QUERY a b",
- The end of each test case is signified by the string "DONE".
There is one blank line between successive tests.
Output
For each "QUERY" operation, write one integer representing its result.
Example
Input:131 2 12 3 2QUERY 1 2CHANGE 1 3QUERY 1 2DONEOutput:13
我也不知道这个oj怎么注册，大概找了一份标程拍了一上午，应该没问题。
就是一个树剖裸题，树单点修改和查询（u，v）路径最大值。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 const int N = 100000 + 11 , inf = 1 << 30; 6 using namespace std ; 7 int n, head[N] , tot = 0,sum; 8 struct id 9 { 10 int fro,nxt,to,val; 11 } E[N<<1]; 12 void add( int u , int v , int val ) 13 { 14 E[++tot] = (id){u,head[u],v,val};head[u] = tot; 15 E[tot+n-1] = (id){v,head[v],u,val};head[v] = tot+n-1; 16 } 17 struct Node 18 { 19 int deep,fa,size,zson,top,pos; 20 } node[N]; 21 struct seg 22 { 23 int l,r,val; 24 }T[N<<2]; int cnt; 25 26 void dfs1( int u, int pre, int dep ) 27 { 28 node[u] = (Node){dep,pre,1,-1}; 29 for(int i = head[u];~i;i = E[i].nxt) 30 { 31 int v = E[i].to ; 32 if( v == pre ) continue; 33 dfs1(v,u,dep+1); 34 node[u].size += node[v].size; 35 if(node[u].zson == -1 || node[v].size > node[node[u].zson].size) node[u].zson = v; 36 } 37 38 } 39 void dfs2(int u ,int p) 40 { 41 node[u].top = p; node[u].pos = ++sum; 42 if(~node[u].zson)dfs2(node[u].zson,node[u].top); 43 for(int i = head[u];~i;i = E[i].nxt) 44 { 45 int v = E[i].to; 46 if(v == node[u].fa || v == node[u].zson)continue; 47 dfs2(v,v); 48 } 49 } 50 51 void Init() 52 { 53 scanf("%d",&n); 54 memset(head,-1,sizeof(head)); 55 tot = 0 , sum = 0,cnt = 1; 56 int a,b,c; 57 for(int i = 1 ; i < n; ++i) 58 { 59 scanf("%d%d%d",&a,&b,&c); 60 add(a,b,c); 61 } 62 dfs1(1,0,0); 63 dfs2(1,1); 64 } 65 66 void updata( int l,int r,int &num, int cp , int val ) 67 { 68 69 if(!num) { num = ++cnt; T[num] = (seg){0,0,-inf};} 70 if( l == r ){ T[num].val = val ; return ;} 71 int mid = ( l + r ) >> 1 ; 72 if(mid >= cp) 73 { 74 updata(l,mid,T[num].l,cp,val) ; 75 T[num].val = T[T[num].l].val; 76 if(T[num].r) T[num].val = max(T[num].val,T[T[num].r].val); 77 } 78 else 79 { 80 updata(mid+1,r,T[num].r,cp,val) ; 81 T[num].val = T[T[num].r].val; 82 if(T[num].l) T[num].val = max(T[num].val,T[T[num].l].val); 83 } 84 85 } 86 87 int query( int l , int r, int num , int L , int R ) 88 { 89 if(l == L && r == R) return T[num].val; 90 int mid = (l + r) >> 1; 91 if(mid >= R)return query(l,mid,T[num].l,L,R); 92 else if(L > mid) return query(mid+1,r,T[num].r,L,R); 93 else return max(query(l,mid,T[num].l,L,mid),query(mid+1,r,T[num].r,mid+1,R)); 94 } 95 96 int lca(int x,int y) 97 { 98 int ans = -inf; 99 while(node[x].top != node[y].top)100 {101 if(node[node[x].top].deep < node[node[y].top].deep) swap(x,y); 102 ans = max(ans , query(1,n,1,node[node[x].top].pos,node[x].pos));103 x = node[node[x].top].fa;104 }105 if( node[x].deep > node[y].deep ) swap(x,y);106 if(x != y)107 ans = max(ans,query(1,n,1,node[x].pos+1,node[y].pos));108 return ans;109 }110 111 112 void Solve()113 {114 char ch[10];115 int a , b; T[1].val = -inf;T[1] = (seg){0,0,-inf};116 for(int i = 1; i < n ; ++i)117 {118 if(node[E[i].fro].deep > node[E[i].to].deep) swap(E[i].fro,E[i].to);119 int now = 1;120 updata(1,n,now,node[E[i].to].pos,E[i].val); 121 } 122 while(~scanf("%s",ch)&&ch[0]!=‘D‘)123 {124 if(ch[0] == ‘Q‘)125 {126 scanf("%d%d",&a,&b);127 printf("%d\n",lca(a,b)); 128 }129 else if(ch[0] == ‘C‘)130 {131 scanf("%d%d",&a,&b);132 int now = 1 ;133 updata(1,n,now,node[E[a].to].pos,b);134 }135 136 }137 }138 139 int main( )140 {141 int t;142 scanf("%d",&t);143 while(t--)144 {145 Init();146 Solve();147 }148 return 0;149 }
spoj375 QTREE - Query on a tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。