首页 > 代码库 > QTREE----树剖

QTREE----树剖

2024-08-17 22:16:12   222人阅读

题目内容：

————————————————————————————————————————————————————

Query on a tree
Time Limit: 851MS   Memory Limit: 1572864KB   64bit IO Format: %lld & %llu

Submit Status

Description

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

——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

第一次写树剖，好长时间写的代码，可是卡了，又过了好长时间才调，又调了好长时间才过。昨天刚刚调试成功。笨啊！！！！！！！！！！！！

树链剖分：就是把树剖成链。
1、剖的依据为子树的大小。最大的为重儿子，其它的为轻儿子。连接重儿子的边为重边，其它的为轻边。重边组成重链。
2、把重链依次放入线段树中，进行维护。

编程过程：

1、读入图（边表）。
2、第一次DFS，维护树中各个点的深度、父亲、子树大小、重儿子。
3、第二次DFS,维护树中各个链的顶节点，和各个节点在线段树中的位置。
4、建空线段树。
5、依次读取各条边（因为边表每边读取2边，所以要隔一条读一条），调整U,V的次序，保证边权落在子节点上，更新子节点在线段树中的位置。
6、读取到更新命令时，依照（5）中的方法更新，但是因为U、V的次序已经调整，则无需调整，只需要更新边2*x-1的子节点即可。
7、读取到查询命令时，首先判断两点是否在一条链上，（a）如果不，查询深度更深的点到它所在链的链顶的最大值，然后让该点更新为链顶点的父亲，并更新链顶继续判断，直到在一条链上为止。（b）如果在一条链上则，2点是否为同一点，如果是则直接返回，否则调整U、v两点的位置，查询u在线段树中位置+1（因为U点代表U上边的边）到v的位置的最大值，更新ans,返回输出。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 
  5 using namespace std;
  6 struct edge
  7 {
  8     int u,v,w,next;
  9 }e[20010];
 10 struct node
 11 {
 12     int l,r,val;
 13     node * lc,* rc;
 14 }*root=NULL;
 15 int t,n;
 16 int head[10010],js,p;
 17 int fa[10010],son[10010],dep[10010],top[10010],siz[10010],fpos[10010],pos[10010];
 18 void init()
 19 {
 20     js=0;
 21     memset(head,0,sizeof(head));
 22     p=0;
 23     memset(e,0,sizeof(e));
 24     memset(son,0,sizeof(son));
 25 }
 26 void addage(int u,int v,int w)
 27 {
 28     e[++js].u=u;e[js].v=v;e[js].w=w;
 29     e[js].next=head[u];head[u]=js;
 30 }
 31 void dfs(int u,int f,int d)//????????????????? 
 32 {
 33     fa[u]=f;dep[u]=d;siz[u]=1;
 34     for(int i=head[u];i;i=e[i].next)
 35     {
 36         int v=e[i].v;
 37         if(v!=f)
 38         {
 39             dfs(v,u,d+1);
 40             siz[u]+=siz[v];
 41             if(!son[u]||siz[son[u]]<siz[v])
 42             son[u]=v;
 43         }
 44     }
 45 }
 46 void getpos(int u,int tp)//??top,pos(????????)
 47 {
 48     top[u]=tp;
 49     pos[u]=++p;
 50 //    fpos[pos[u]]=u;
 51     if(!son[u])return;
 52     getpos(son[u],tp);
 53     for(int i=head[u];i;i=e[i].next)
 54     {
 55         int v=e[i].v;
 56         if(v!=son[u]&&v!=fa[u])
 57             getpos(v,v);
 58     }
 59 }
 60 void build(node * &pt,int l,int r)
 61 {
 62     pt=new(node);
 63     pt->l=l;pt->r=r;pt->val=0;
 64     if(l==r)
 65     {
 66         pt->lc=pt->rc=NULL;
 67         return ;
 68     }
 69     int mid=(l+r)/2;
 70     build(pt->lc,l,mid);
 71     build(pt->rc,mid+1,r);
 72 }
 73 void update(node * p,int ps,int val)
 74 {
 75     if(p->l==p->r)
 76     {
 77         p->val=val;
 78         return ;
 79     }
 80     int mid=(p->l+p->r)/2;
 81     if(ps<=mid)update(p->lc,ps,val);
 82     else update(p->rc,ps,val);
 83     p->val=max(p->lc->val,p->rc->val);
 84 }
 85 int query(node * p,int l,int r)
 86 {
 87     if(l<=p->l&&p->r<=r)return p->val;
 88     int mid=(p->l+p->r)/2;
 89     int ans=0;
 90     if(l<=mid)ans=max(ans,query(p->lc,l,r));
 91     if(r>mid)ans=max(ans,query(p->rc,l,r));
 92     return ans;
 93 }
 94 int find(int u,int v)
 95 {
 96     int tp1=top[u],tp2=top[v],ans=0;
 97     while(tp1!=tp2)
 98     {
 99         if(dep[tp1]<dep[tp2])
100         {
101             swap(tp1,tp2);
102             swap(u,v);
103         }
104         ans=max(ans,query(root,pos[tp1],pos[u]));
105         u=fa[tp1];tp1=top[u];
106     }
107     if(u==v)return ans;
108     if(dep[u]>dep[v])swap(u,v);
109     return max(ans,query(root,pos[u]+1,pos[v]));
110 }
111 int main()
112 {
113     cin>>t;
114     while(t--)
115     {
116         init();
117         scanf("%d",&n);
118         for(int i=1;i<n;i++)
119         {
120             int a,b,c;
121             scanf("%d%d%d",&a,&b,&c);
122             addage(a,b,c);
123             addage(b,a,c);
124         }
125         dfs(1,0,1);
126         getpos(1,1); 
127         build(root,1,p);
128         for(int i=1;i<2*n-2;i+=2)
129         {
130             if(dep[e[i].v]<dep[e[i].u])swap(e[i].v,e[i].u);
131             update(root,pos[e[i].v],e[i].w);
132 //            cout<<e[i].u<<"------"<<e[i].v<<"-----"<<endl;
133         }
134         char s[10];
135         int u,v;
136         while(scanf("%s",s)==1)
137         {
138             if(s[0]==‘D‘)break;
139             scanf("%d%d",&u,&v);
140             if(s[0]==‘Q‘)printf("%d\n",find(u,v));
141             else update(root,pos[e[u*2-1].v],v);
142         }
143     }
144     return 0;
145 }

 

QTREE----树剖


联系
我们