题目描述
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
输入输出格式
输入格式：
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.
输出格式：
For each "QUERY" operation, write one integer representing its result.
输入样例：
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
输出样例：
1
3
#include<bits/stdc++.h>
using namespace std;
const int N = 10005, oo = 0x7fffffff;
struct Edge{ int to,next; }edge[N<<1];
struct Bian{ int a,b,c; } bian[N];
int t,n,en,head[N],w[N];
int father[N],depth[N],size[N],son[N];
int top[N],seg[N],rev[N];
int Max[N<<2],maxx;
inline void read(int &x){
char last=' ',ch;
while ((ch=getchar())<'0' || ch>'9') last=ch;
for (x=0;ch>='0' && ch<='9';ch=getchar())
x = x*10+ch-'0';
if (last=='-') x = -x;
}
inline void add(int x,int y){
edge[en].to = y;
edge[en].next = head[x];
head[x] = en++;
}
void init(){
read(n);
memset(head,-1,sizeof(head));
en = 0;
for (int i=1;i<n;i++) {
read(bian[i].a);
read(bian[i].b);
read(bian[i].c);
add(bian[i].a,bian[i].b);
add(bian[i].b,bian[i].a);
}
memset(top,0,sizeof(top));
memset(son,0,sizeof(son));
memset(father,0,sizeof(father));
memset(depth,0,sizeof(depth));
memset(size,0,sizeof(size));
memset(w,0,sizeof(w));
fill(Max,Max+n*4,-oo);
}
void dfs1(int u,int f){
father[u] = f;
depth[u] = depth[f] + 1;
size[u] = 1;
for (int v,p=head[u]; ~p; p=edge[p].next){
v = edge[p].to ;
if (v == f) continue;
dfs1(v,u);
size[u] += size[v];
if (size[v]>size[son[u]])
son[u] = v;
}
}
inline void dealbian(){
for (int i=1;i<n;i++){
if (father[bian[i].b]!=bian[i].a) swap(bian[i].a,bian[i].b);
w[bian[i].b] = bian[i].c ;
}
}
void dfs2(int u){
if (son[u]){
top[son[u]] = top[u];
seg[son[u]] = ++seg[0];
rev[seg[0]] = son[u];
dfs2(son[u]);
}
for (int v,p=head[u]; ~p; p=edge[p].next ){
v = edge[p].to ;
if (top[v]) continue;
top[v] = v;
seg[v] = ++seg[0];
rev[seg[0]] = v;
dfs2(v);
}
}
inline void pushup(int root){
Max[root] = max(Max[root<<1],Max[root<<1|1]);
}
void create(int root,int L,int R){
if (L==R){
Max[root] = w[rev[L]];
return;
}
int mid = (L+R)>>1;
create(root<<1, L, mid);
create(root<<1|1, mid+1, R);
pushup(root);
}
void update(int root,int L,int R,int x,int y){
if (L==R){
Max[root] = y;
return ;
}
int mid = (L+R)>>1;
if (x<=mid) update(root<<1,L,mid,x,y);
else update(root<<1|1,mid+1,R,x,y);
pushup(root);
}
void query(int root,int L,int R,int x,int y){
if (L>y || R<x) return ;
if (x<=L && R<=y) {
maxx = max(maxx,Max[root]);
return;
}
int mid = (L+R)>>1;
query(root<<1,L,mid,x,y);
query(root<<1|1,mid+1,R,x,y);
}
void chaxun(int x,int y){
while (top[x]!=top[y]){
if (depth[top[x]]<depth[top[y]]) swap(x,y);
query(1,1,n,seg[top[x]],seg[x]);
x = father[top[x]];
}
if (x==y) return;
if (depth[x]>depth[y]) swap(x,y);
int t=w[x];
w[x] = -oo;
query(1,1,n,seg[x],seg[y]);
w[x] = t;
}
void solve(){
char cmd[10];
int i,ti,a,b;
while (~scanf("%s",cmd) && cmd[0]!='D'){
switch (cmd[0]){
case 'C': read(i); read(ti);
a = bian[i].a;
b = bian[i].b;
if (father[b]!=a) swap(a,b);
update(1,1,n,seg[b],ti);
break;
case 'Q': read(a); read(b);
maxx = -oo;
chaxun(a,b);
printf("%d\n",maxx);
break;
}
}
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
read(t);
while (t--){
init();
dfs1(1,0);
dealbian();
top[1] = seg[0] = seg[1] = rev[1] = 1;
dfs2(1);
create(1,1,n);
solve();
}
return 0;
}
posted on 2019-03-01 00:58
龙在江湖 阅读(109)
评论(0) 编辑 收藏 引用 所属分类:
图论