Spoj Query on a tree SPOJ - QTREE(树链剖分+线段树)
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:
1
3
/*
树链剖分+线段树.
这题呵呵了.
询问字符串竟然卡cin(长记性了).
化边为点.
建树后把边的信息存在son里.
因为son只有一个father,而father可以同时有若干个son.
树剖线段树单点修改区间查询.
这题一开始W的原因是
here:query(1,pos[x],pos[y]).
应该为query(1,pos[x]+1,pos[y]).
因为我们已经把边的信息存到son里边了.
pos[x]存的是(x,fa[x])的edge.
然而我们最后查的是[x,y]的ans.
所以从x的son开始查.
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 100001
using namespace std;
struct edge{int v,next;}e[MAXN*2];
struct data{int l,r,lc,rc,ans;}tree[MAXN*4];
int n,m,ans,head[MAXN],cut,size[MAXN],fa[MAXN],top[MAXN],deep[MAXN],maxsize,pos[MAXN];
struct node{int x,y,z;}s[MAXN];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void add(int u,int v,int x)
{
e[++cut].v=v;
e[cut].next=head[u];
head[u]=cut;
}
void build(int l,int r)
{
int k=++cut;
tree[k].l=l,tree[k].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
tree[k].lc=cut+1;build(l,mid);
tree[k].rc=cut+1;build(mid+1,r);
return ;
}
void dfs1(int u)
{
size[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(!fa[v]) deep[v]=deep[u]+1,fa[v]=u,dfs1(v),size[u]+=size[v];
}
return ;
}
void dfs2(int u,int top1)
{
top[u]=top1;pos[u]=++maxsize;
int k=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(fa[v]==u&&size[v]>size[k]) k=v;
}
if(!k) return ;
dfs2(k,top1);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(fa[v]==u&&v!=k) dfs2(v,v);
}
return ;
}
void change(int k,int x,int z)
{
if(tree[k].l==tree[k].r)
{
tree[k].ans=z;return ;
}
int mid=(tree[k].l+tree[k].r)>>1;
if(x<=mid) change(tree[k].lc,x,z);
else change(tree[k].rc,x,z);
tree[k].ans=max(tree[tree[k].lc].ans,tree[tree[k].rc].ans);
return ;
}
int query(int k,int l,int r)
{
if(l<=tree[k].l&&tree[k].r<=r) return tree[k].ans;
int tot=-1e9,mid=(tree[k].l+tree[k].r)>>1;
if(l<=mid) tot=max(tot,query(tree[k].lc,l,r));
if(r>mid) tot=max(tot,query(tree[k].rc,l,r));
return tot;
}
int slovequery(int x,int y)
{
ans=-1e9;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,query(1,pos[top[x]],pos[x]));
x=fa[top[x]];
}
if(pos[x]>pos[y]) swap(x,y);
ans=max(ans,query(1,pos[x]+1,pos[y]));//1 W.
return ans;
}
void Clear()
{
cut=0;maxsize=0;
memset(head,0,sizeof head);
memset(size,0,sizeof size);
memset(fa,0,sizeof fa);
memset(tree,0,sizeof tree);
}
int main()
{
int x,y,z,p,q,t;
t=read();
while(t--)
{
n=read();Clear();
for(int i=1;i<=n-1;i++)
{
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
s[i].x=x,s[i].y=y,s[i].z=z;
}
cut=0;
build(1,n);fa[1]=1;
dfs1(1),dfs2(1,1);
for(int i=1;i<=n-1;i++)
{
x=s[i].x,y=s[i].y;
if(fa[x]==y) swap(x,y);
change(1,pos[y],s[i].z);
}
char ch[6];
while(true)
{
scanf("%s",ch);
//cin>>ch; 1T
if(ch[0]=='D') break;
x=read(),y=read();
if(ch[0]=='Q') printf("%d\n",slovequery(x,y));
else
{
p=s[x].x,q=s[x].y;
if(fa[p]==q) swap(p,q);
change(1,pos[q],y);
}
}
}
return 0;
}
最新文章
- React Diff算法
- iOS-最全的App上架教程
- SQL Server复制需要有实际的服务器名称才能连接到服务器
- laravel5学习手记
- 不规则三角网 Delaunay——TIN
- Bootstrap的aria-label与aria-labelledby
- HTML学习笔记(七)
- 完美解决夏天电脑cpu发烫问题
- Spring AOP分析(3) -- CglibAopProxy实现AOP
- 深入理解[Master-Worker模式]原理与技术
- luogu3674 小清新人渣的本愿 (bitset+莫队)
- 【python小练】图片爬虫之BeautifulSoup4
- springboot11-01-security入门
- charles 注册码
- 由自定义事件到vue数据响应
- python写xml及几个问题
- redis集群服务启动
- 文档撰写思路与排版(hadoop)
- 使用Java实现网络爬虫
- java第六天