此题需要把边权转换成点权，方法如下：
可以从根开始dfs，然后将每条边的值赋到向下的一个节点上，最后再把根的值赋为-∞即可。例如有一条1到2的边，权值为3，则从1开始dfs，就将2这个点的点权赋为3。
|
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 |
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int T,n,tot,Head[20010],label,Next[20010],tree[20010],val[20010],a[80080],f[10010],bian[10010]; int size[10010],son[10010],num[10010],tid[10010],top[10010],fa[10010],dep[10010],number[20010]; bool visit[10010]; void Add(int x,int y,int z,int Num) { tot++; Next[tot]=Head[x]; Head[x]=tot; tree[tot]=y; val[tot]=z; number[tot]=Num; } void up(int x) { a[x]=max(a[x*2],a[x*2+1]); } void build(int id,int l,int r) { if (l==r) { a[id]=f[num[l]]; return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); up(id); } void Change_it(int x,int y,int d,int id,int l,int r)//此题单点修改 { if (l>y||r<x) return; if (l>=x&&r<=y) { a[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); up(id); } int Query_it(int x,int y,int id,int l,int r) { if (l>y||r<x) return(-1<<29); if (l>=x&&r<=y) return a[id]; int mid=(l+r)/2; int ans=max(Query_it(x,y,id*2,l,mid),Query_it(x,y,id*2+1,mid+1,r)); return ans; } void Find_heavy_edge(int x,int father,int depth) { fa[x]=father;dep[x]=depth; visit[x]=true;size[x]=1;son[x]=0; int maxsize=0; for (int i=Head[x];i;i=Next[i]) if (!visit[tree[i]]) { f[tree[i]]=val[i];bian[number[i]]=tree[i]; Find_heavy_edge(tree[i],x,depth+1); size[x]+=size[tree[i]]; if (maxsize<size[tree[i]]) { maxsize=size[tree[i]]; son[x]=tree[i]; } } } void Connect_heavy_edge(int x,int ancestor) { visit[x]=true; label++;tid[x]=label;num[label]=x;top[x]=ancestor; if (son[x]!=0) Connect_heavy_edge(son[x],ancestor); for (int i=Head[x];i;i=Next[i]) if (!visit[tree[i]]) { Connect_heavy_edge(tree[i],tree[i]); } } 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() { scanf("%d",&T); for (int cas=1;cas<=T;cas++) { scanf("%d",&n); tot=0; for (int i=1;i<=n;i++) Head[i]=0; for (int i=1;i<=n-1;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); Add(x,y,z,i);Add(y,x,z,i); } int root=1; f[root]=-1<<27; label=0; for (int i=1;i<=n;i++) visit[i]=false; Find_heavy_edge(root,0,1); for (int i=1;i<=n;i++) visit[i]=false; Connect_heavy_edge(root,root); build(1,1,n); char s[10]; int x,y; while (true) { scanf("%s",s); if (s[0]=='D') break; scanf("%d%d",&x,&y); if (s[0]=='Q') printf("%d\n",Query(x,y)); else Change_it(tid[bian[x]],tid[bian[x]],y,1,1,n); } } return 0; } |
