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:
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
Output:
13
之前用动态树写了一下，，动态树稍微快点，实在是无语，不知道为什么注释的那点线段树写法怎么错了，着急上课以后再说
| 15342170 | 2015-10-11 12:36:49 |
略懂_is_a_Joker | Query on a tree |
acceptededit ideone it |
0.69 | 4.5M | C++ 5 |
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define max(a,b) (a>b?a:b)
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define N 10010
int U[N],V[N],W[N],head[N],cnt;
int top[N],p[N],fa[N],deep[N],son[N],fp[N],num[N];
int pos;
struct s
{
int u,v,w,next;
}edge[N<<1];
void add(int u,int v,int w)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u,int pre,int d)
{
deep[u]=d;
fa[u]=pre;
num[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v==pre)
continue;
dfs(v,u,d+1);
num[u]+=num[v];
if(son[u]==-1||num[v]>num[son[u]])
son[u]=v;
}
}
void getpos(int u,int sp)
{
top[u]=sp;
if(son[u]!=-1)
{
p[u]=pos++;
fp[p[u]]=u;
getpos(son[u],sp);
}
else
{
p[u]=pos++;
fp[p[u]]=u;
return;
}
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v!=son[u]&&v!=fa[u])
getpos(v,v);
}
}
int node[N<<2];
void pushup(int tr)
{
node[tr]=max(node[tr<<1],node[tr<<1|1]);
}
void build(int l,int r,int tr)
{
node[tr]=0;
if(l==r)
return;
int mid=(l+r)>>1;
build(l,mid,tr<<1);
build(mid+1,r,tr<<1|1);
}
void update(int pos,int val,int l,int r,int tr)
{
if(l==r)
{
node[tr]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
{
update(pos,val,l,mid,tr<<1);
}
else
update(pos,val,mid+1,r,tr<<1|1);
pushup(tr);
}
/*int query(int L,int R,int l,int r,int tr)
{
if(L<=l&&r<=R)
{
return node[tr];
}
int mid=(l+r)>>1;
int a,b;
if(L<=mid)
a=query(L,R,l,mid,tr<<1);
if(R>mid)
b=query(L,R,mid+1,r,tr<<1|1);
return max(a,b);
}*/
int query(int L,int R,int l,int r,int tr)
{
if(l==L&&R==r)
{
return node[tr];
}
int mid=(l+r)>>1;
if(R<=mid)
return query(L,R,l,mid,tr<<1);
else
if(L>mid)
return query(L,R,mid+1,r,tr<<1|1);
else
return max(query(L,mid,l,mid,tr<<1),query(mid+1,R,mid+1,r,tr<<1|1));
}
int solve(int u,int v)
{
int f1=top[u];
int f2=top[v];
int temp=0;
while(f1!=f2)
{
if(deep[f1]<deep[f2])
{
swap(u,v);
swap(f1,f2);
}
temp=max(temp,query(p[f1],p[u],0,pos-1,1));
u=fa[f1];
f1=top[u];
}
if(u==v)
{
return temp;
}
if(deep[u]>deep[v])
{
swap(u,v);
}
return max(temp,query(p[son[u]],p[v],0,pos-1,1));
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int i;
cnt=0;
memset(head,-1,sizeof(head));
memset(son,-1,sizeof(son));
//memset(node,0,sizeof(node));
pos=0;
for(i=0;i<n-1;i++)
{
scanf("%d%d%d",&U[i],&V[i],&W[i]);
add(U[i],V[i],W[i]);
add(V[i],U[i],W[i]);
}
dfs(1,0,0);
getpos(1,1);
build(0,pos-1,1);
char op[10];
for(i=0;i<n-1;i++)
{
if(deep[U[i]]>deep[V[i]])
swap(U[i],V[i]);
update(p[V[i]],W[i],0,pos-1,1);
}
while(scanf("%s",op)==1)
{
if(op[0]=='D')
break;
int u,v;
scanf("%d%d",&u,&v);
if(op[0]=='Q')
{
printf("%d\n",solve(u,v));
}
else
update(p[V[u-1]],v,0,pos-1,1);
}
}
}