题目：
You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:
CHANGE i v |
Change the weight of the ith edge to v |
NEGATE a b |
Negate the weight of every edge on the path from a to b |
QUERY a b |
Find the maximum weight of edges on the path from a to b |
这题同样需要将边权转换成点权。
题目链接
另一道需要将边权转换成点权的题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
#include<iostream> #include<cstdio> using namespace std; int n,tot,label,tree[80010],Next[20010],head[10010],tree1[20010],val[20010],num[20010],dep[10010]; int top[10010],tid[10010],edge[10010],fa[10010],son[10010],size[10010],a[10010],flag[10010]; bool visit[10010]; void swap(int &x,int &y) { int t=x;x=y;y=t; } int max(int i,int j) { if (i>j) return i;else return j; } void Add(int x,int y,int z,int number) { tot++; Next[tot]=head[x]; head[x]=tot; tree1[tot]=y; val[tot]=z; num[tot]=number; } void build(int id,int l,int r) { if (l==r) { tree[id]=a[flag[l]]; return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); tree[id]=max(tree[id*2],tree[id*2+1]); } void dfs(int x,int father,int depth) { visit[x]=true;dep[x]=depth;fa[x]=father;son[x]=0;size[x]=1; int maxsize=0; for (int i=head[x];i;i=Next[i]) if (!visit[tree1[i]]) { a[tree1[i]]=val[i];edge[num[i]]=tree1[i]; dfs(tree1[i],x,depth+1); size[x]+=size[tree1[i]]; if (size[tree1[i]]>maxsize) { maxsize=size[tree1[i]]; son[x]=tree1[i]; } } } void dfs1(int x,int ancestor) { top[x]=ancestor;visit[x]=true; label++;tid[x]=label;flag[label]=x; if (son[x]!=0) dfs1(son[x],ancestor); for (int i=head[x];i;i=Next[i]) if (!visit[tree1[i]]) dfs1(tree1[i],tree1[i]); } void change_it(int x,int y,int d,int id,int l,int r) { if (r<x||l>y) return; if (l==r) //此题单点修改值，所以这里x=y { tree[id]=d; return; } int mid=(l+r)/2; change_it(x,y,d,id*2,l,mid); change_it(x,y,d,id*2+1,mid+1,r); tree[id]=max(tree[id*2],tree[id*2+1]); } void negate_it(int x,int y,int id,int l,int r) { if (r<x||l>y) return; if (l==r&&x<=l&&r<=y) { tree[id]=-tree[id]; return; } int mid=(l+r)/2; negate_it(x,y,id*2,l,mid); negate_it(x,y,id*2+1,mid+1,r); tree[id]=max(tree[id*2],tree[id*2+1]); } int query_it(int x,int y,int id,int l,int r) { if (r<x||l>y) return -1<<29; if (x<=l&&r<=y) return tree[id]; int mid=(l+r)/2; return max(query_it(x,y,id*2,l,mid),query_it(x,y,id*2+1,mid+1,r)); } void change(int x,int y,int d) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); change_it(tid[top[x]],tid[x],d,1,1,n); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); change_it(tid[x],tid[y],d,1,1,n); } void negate1(int x,int y) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); negate_it(tid[top[x]],tid[x],1,1,n); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); negate_it(tid[x]+1,tid[y],1,1,n); } int query(int x,int y) { int ans=-1<<29; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,query_it(tid[top[x]],tid[x],1,1,n)); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans=max(ans,query_it(tid[x]+1,tid[y],1,1,n)); return ans; } int main() { int T; scanf("%d",&T); for (int cas=1;cas<=T;cas++) { scanf("%d",&n); for (int i=1;i<=n;i++) head[i]=0; tot=0;label=0; for (int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); Add(x,y,z,i);Add(y,x,z,i); } for (int i=1;i<=n;i++) visit[i]=false; a[1]=-1<<29; dfs(1,0,1); for (int i=1;i<=n;i++) visit[i]=false; dfs1(1,1); build(1,1,n); char s[10]; while (true) { scanf("%s",s); if (s[0]=='D') break; if (s[0]=='C') { int x,d; scanf("%d%d",&x,&d); change(edge[x],edge[x],d); } if (s[0]=='N') { int x,y; scanf("%d%d",&x,&y); negate1(x,y); } if (s[0]=='Q') { int x,y; scanf("%d%d",&x,&y); printf("%d\n",query(x,y)); } } } return 0; } |
