首页 > 代码库 > hdu5044 Tree
hdu5044 Tree
Tree
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 845 Accepted Submission(s): 162
Problem Description
You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N
There are N - 1 edges numbered from 1 to N - 1.
Each node has a value and each edge has a value. The initial value is 0.
There are two kind of operation as follows:
● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.
● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.
After finished M operation on the tree, please output the value of each node and edge.
There are N - 1 edges numbered from 1 to N - 1.
Each node has a value and each edge has a value. The initial value is 0.
There are two kind of operation as follows:
● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.
● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.
After finished M operation on the tree, please output the value of each node and edge.
Input
The first line of the input is T (1 ≤ T ≤ 20), which stands for the number of test cases you need to solve.
The first line of each case contains two integers N ,M (1 ≤ N, M ≤105),denoting the number of nodes and operations, respectively.
The next N - 1 lines, each lines contains two integers u, v(1 ≤ u, v ≤ N ), denote there is an edge between u,v and its initial value is 0.
For the next M line, contain instructions “ADD1 u v k” or “ADD2 u v k”. (1 ≤ u, v ≤ N, -105 ≤ k ≤ 105)
The first line of each case contains two integers N ,M (1 ≤ N, M ≤105),denoting the number of nodes and operations, respectively.
The next N - 1 lines, each lines contains two integers u, v(1 ≤ u, v ≤ N ), denote there is an edge between u,v and its initial value is 0.
For the next M line, contain instructions “ADD1 u v k” or “ADD2 u v k”. (1 ≤ u, v ≤ N, -105 ≤ k ≤ 105)
Output
For each test case, print a line “Case #t:”(without quotes, t means the index of the test case) at the beginning.
The second line contains N integer which means the value of each node.
The third line contains N - 1 integer which means the value of each edge according to the input order.
The second line contains N integer which means the value of each node.
The third line contains N - 1 integer which means the value of each edge according to the input order.
Sample Input
24 21 22 32 4ADD1 1 4 1ADD2 3 4 24 21 22 31 4ADD1 1 4 5ADD2 3 2 4
Sample Output
Case #1:1 1 0 10 2 2Case #2:5 0 0 50 4 0
Source
2014 ACM/ICPC Asia Regional Shanghai Online
思路：先求lca，对于点的修改，对于 u,v，假设 lca等于 u ,那么add[v] += val ;add[fa[u]] -= val ;
如果lca不为 u,v那么 ......看代码吧，
最后从根节点开始 up , add[fa] += add[son] ; 这个add[u]，就是u 增加的值
对于边的修改，我们先转为有根树，然后把边的权值分给两个端点中，深度高的那个，然后
就可以和点修改差不多了，具体看代码吧
这题真吭，很和谐的树链分割过不了。。。。
#pragma comment(linker,"/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define INF 999999#define mod 20140518#define maxn 100010using namespace std;int head[maxn],next1[maxn*2],to[maxn*2] ;int top ,id[maxn] ,n ,num[maxn],dep[maxn];int xx[maxn],yy[maxn],cc[maxn],e[maxn];int fa[maxn];LL ans[maxn],add1[maxn],add2[maxn];int out[maxn];bool vi[maxn] ;struct node{ int v,id; node(){} node(int x,int y ) { v = x ;id = y ; }};vector<node>qe[maxn];void Unit(int u,int v ){ next1[top] = head[u] ;to[top] = v ; head[u] = top++;}int find(int x ){ if(x != fa[x]) fa[x] = find(fa[x]) ; return fa[x];}void dfs(int u ,int f){ fa[u]=u; vi[u] = true; for(int i = head[u] ; i != -1 ; i = next1[i]) { int v = to[i] ; if(v==f) continue; dfs(v,u) ; fa[v] = u ; } node a; for(int i = 0 ; i < qe[u].size();i++) { a = qe[u][i] ; if(!vi[a.v]) continue ; num[a.id] = find(a.v) ; }}void bfs(int s){ memset(vi,0,sizeof(vi)) ; memset(out,0,sizeof(out)); queue<int>q ; q.push(s) ; dep[s]=0; vi[s] = true ; while(!q.empty()) { int u = q.front() ; q.pop() ; for(int i = head[u] ; i != -1 ; i = next1[i]) { int v = to[i] ; if(vi[v]) continue ; out[u]++; vi[v] = true ; dep[v]=u; id[v] = i/2+1 ; q.push(v) ; } }}int next_int() { char ch; int res; bool neg; while (ch = getchar(), !isdigit(ch) && ch != ‘-‘) ; if (ch == ‘-‘) { neg = true; res = 0; } else { neg = false; res = ch - ‘0‘; } while (ch = getchar(), isdigit(ch)) res = res * 10 + ch - ‘0‘; return neg ? -res : res;}int main(){ char a[10] ; int m,x,y,i,j,u,v; int T,c ,case1=0; cin >> T ; while( T-- ) { scanf("%d%d",&n,&m) ; for(i = 0 ; i <= n ;i++)qe[i].clear(); memset(head,-1,sizeof(head)) ; top=0; for( i = 1 ; i < n ;i++) { x = next_int(); y = next_int(); Unit(x,y) ; Unit(y,x) ; } bfs(1) ; for( i = 1 ; i <= m ;i++) { scanf("%s",a) ; x = next_int(); y = next_int(); c = next_int(); qe[x].push_back(node(y,i)); qe[y].push_back(node(x,i)); xx[i]=x;yy[i]=y; cc[i]=c; if(a[3]==‘1‘) { e[i]=1; } else { e[i]=0; } } memset(vi,0,sizeof(vi)) ; memset(add1,0,sizeof(add1)); memset(add2,0,sizeof(add2)); dfs(1,-1); int f; for( i = 1 ; i <= m ;i++) { f = num[i]; u=xx[i]; v=yy[i]; if(e[i]) { if(u==v) { add1[u] += cc[i]; add1[dep[f]] -= cc[i]; } else{ add1[u] += cc[i]; add1[v] += cc[i]; add1[dep[f]] -= cc[i]; add1[f] -= cc[i]; } } else{ if(u==v) { add2[u] += cc[i]; add2[f] -= cc[i]; } else{ add2[u] += cc[i]; add2[v] += cc[i]; add2[f] -= 2*cc[i]; } } } queue<int>q; for( i = 1 ; i <= n ;i++)if(!out[i]) { q.push(i); } memset(vi,0,sizeof(vi)); while(!q.empty()) { u = q.front();q.pop(); v = dep[u] ; if(v==0) continue ; add1[v] += add1[u] ; add2[v] += add2[u] ; out[v]--; if(out[v]==0)q.push(v); } printf("Case #%d:\n",++case1); bool flag=false; for( i = 1 ; i <= n ;i++) { if(flag)printf(" ") ; flag=true; printf("%I64d",add1[i]); } puts(""); flag=false; for( i = 2 ; i <= n ;i++) { ans[id[i]] = add2[i]; } for( i = 1 ; i <n ;i++) { if(flag) printf(" ") ; flag=true; printf("%I64d",ans[i]); } puts(""); } return 0 ;}
hdu5044 Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。