QTREE----树剖
2024-08-31 12:56:47
题目内容：
————————————————————————————————————————————————————
| Time Limit: 851MS | Memory Limit: 1572864KB | 64bit IO Format: %lld & %llu |
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 }
最新文章
- sql server 查看表的死锁和Kill 死锁进程
- MySQL 主键范围查找问题
- easyui datagrid 学习
- JS定时执行，循环执行
- leetcode面试准备:Simplify Path
- （转）PHP函数之error_reporting(E_ALL ^ E_NOTICE)详细说明
- border做箭头的例子
- Swift中的便利构造器和构造器链
- python 3.5 格式化字符串输出
- 利用QrCode.Net生成二维码 asp.net mvc c#
- 看到一个想收藏的的AJAX小列子
- 《nginx - 基本操作/配置》
- Git应用—02各种冲突场景处理（转载）
- JavaScript之浏览器兼容问题与IE(神经病一样的浏览器)
- plsql连接oracle数据库，不用配置任何东西（转）
- python短信发送
- 安装spring-tool-suite插件
- web中显示中文名称的图片，可以这样配置filter
- 第十四章 Executors源码解析
- 第三天，爬取伯乐在线文章代码，编写items.py，保存数据到本地json文件中