题目大意：给个无向图，每条边有个限制，每个点最多能买入和卖出一定黄金；然后按顺序走过n个点，求每个卖出黄金的点最多能卖出多少黄金
一开始有点懵，想着怎么再图上做这个问题，后来知道要先建一棵最大生成树
然后就好做了，做的时候黄金全都拿，不必考虑第一个条件，因为就算花不完也能在之前某个地方少买一点黄金
然后没个询问找前后两个点lca，求路径上的最小边的限制，这样就可以求出卖出多少黄金了
最后要谴责一下非常脑残的数据，有个数据点是两条链，dfs时会爆栈= =，WA了我两天十几次
话说出数据时不应该这样戏弄别人，非常浪费时间和精力又没有意义
一定要手写栈！！
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define LL long long 5 #define INF 21474836470000 6 using namespace std; 7 const int maxn = 100010; 8 struct node{ 9 int from,to,next; 10 LL cost; 11 }E[maxn*2],e[maxn*2]; 12 int n,m,q,trade[maxn],fa[maxn][21],Fa[maxn],dep[maxn],head[maxn],tot,logn,order[maxn],scc[maxn],bel,st[maxn*10]; 13 LL pre[maxn][21]; 14 15 void insert(int u, int v, LL c){ 16 e[++tot].to=v; e[tot].next=head[u]; e[tot].cost=c; head[u]=tot; 17 } 18 19 bool cmp(node a, node b){ 20 return a.cost>b.cost; 21 } 22 23 int find(int x){ 24 return Fa[x]==x?x:Fa[x]=find(Fa[x]); 25 } 26 27 void dfs(int u, int f){ 28 int top=0; 29 st[++top]=u; 30 while (top){ 31 u=st[top--]; f=fa[u][0]; 32 dep[u]=dep[f]+1; 33 for (int i=1; i<=logn; i++) fa[u][i]=fa[fa[u][i-1]][i-1]; 34 for (int i=1; i<=logn; i++) pre[u][i]=min(pre[u][i-1],pre[fa[u][i-1]][i-1]); 35 for (int i=head[u]; i; i=e[i].next) 36 if (e[i].to!=f){ 37 fa[e[i].to][0]=u; 38 pre[e[i].to][0]=e[i].cost; 39 st[++top]=e[i].to; 40 } 41 } 42 } 43 44 LL lca(int u, int v){ 45 LL ret=INF; 46 if (dep[u]<dep[v]) swap(u,v); 47 while (dep[u]>dep[v]){ 48 for (int i=logn; i>=0; i--) 49 if (dep[fa[u][i]]>dep[v]){ 50 ret=min(ret,pre[u][i]); 51 u=fa[u][i]; 52 } 53 ret=min(ret,pre[u][0]); 54 u=fa[u][0]; 55 } 56 if (u==v) return ret; 57 for (int i=logn; i>=0; i--) 58 if (fa[u][i]!=fa[v][i]){ 59 ret=min(ret,pre[u][i]); 60 ret=min(ret,pre[v][i]); 61 u=fa[u][i]; v=fa[v][i]; 62 } 63 ret=min(ret,min(pre[v][0],pre[u][0])); 64 return ret; 65 } 66 67 int main(){ 68 //freopen("motorcycle6.in","r",stdin); 69 //freopen("test.out","w",stdout); 70 scanf("%d%d%d", &n, &m, &q); 71 while ((1<<logn)<n) logn++; tot=1; 72 memset(pre,50,sizeof(pre)); 73 for (int i=1; i<=n; i++) scanf("%d", &order[i]),Fa[i]=i;// shunxu 74 for (int i=1; i<=n; i++) scanf("%d", &trade[i]);// yaoqiu 75 for (int i=1; i<=m; i++) scanf("%d%d%lld", &E[i].from, &E[i].to, &E[i].cost); 76 bel=n; 77 for (int i=1,x; i<=q; i++) scanf("%d", &x),scc[x]=1,bel=min(bel,x); 78 79 sort(E+1,E+1+m,cmp); 80 int num; if (!q) num=n-1; else num=n-q; 81 for (int i=1,hehe=0; i<=m; i++){ 82 int x=E[i].from, y=E[i].to; 83 if (scc[x]) x=bel; if (scc[y]) y=bel; 84 int fx=find(x), fy=find(y); 85 if (fx!=fy){ 86 Fa[fx]=fy; 87 insert(x,y,E[i].cost); 88 insert(y,x,E[i].cost); 89 hehe++; 90 if (hehe==num) break; 91 } 92 } 93 fa[1][0]=0; 94 dfs(1,0); 95 LL now=0; 96 if (trade[order[1]]<0) puts("0"); else now=trade[order[1]]; 97 for (int i=2; i<=n; i++){ 98 int x=order[i-1], y=order[i]; 99 if (scc[x]) x=bel; if (scc[y]) y=bel; 100 now=min(now,lca(x,y)); 101 x=order[i-1]; y=order[i]; 102 if (trade[y]>0) now+=(LL)trade[y]; 103 else{ 104 if (now+(LL)trade[y]>0){ 105 now+=(LL)trade[y]; 106 printf("%d ", -trade[y]); 107 }else{ 108 printf("%lld ", now); 109 now=0LL; 110 } 111 } 112 //printf("%lld ", now); 113 } 114 return 0; 115 }