对于题意 如果想要获取的硬币数最多,也就是所走的路径和最大,再想一下就是除了t到s这条路外其他的路都是一定能做一遍的(ps 题目给的是一棵树)。
题目就可以理解为 给定2个点求之间的路径;
所有边长减去这两点路径就是答案;
维护一个根节点到其他点的路径长度 d
维护一个其他节点到根节点路径长度 d1;
给定s t;
所以 d1[s]+d[t]-d[lca(s,t)]-d1[lca(s,t)])即为2点之间的路径长度,
#include#include #include #include #include #include #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define sc(x) scanf("%d",&(x))#define inf 0x3f3f3f3fusing namespace std;const int maxn=1e5+10;struct edge{ int u,v,w,w1,next;}e[maxn*2];int g[maxn*2],tot=0,d[maxn],d1[maxn];int n,dep[maxn];void make(int u,int v,int w,int w1){ e[++tot]=(edge){u,v,w,w1,g[u]}; g[u]=tot;}int fa[maxn],fathers[maxn][33];void deep(int u,int v,int de,int dd,int td){ fa[u]=v; fathers[u][0]=v; dep[u]=de; for(int i=g[u];i>0;i=e[i].next){ if(e[i].v==v) continue; d1[e[i].v]=dd+e[i].w; d[e[i].v]=td+e[i].w1; deep(e[i].v,u,de+1,dd+e[i].w,td+e[i].w1); }}void ben(){ int d=log(n)/log(2)+1; for(int k=1;k<=d;k++) for(int i=1;i<=n;i++) { fathers[i][k]=fathers[fathers[i][k-1]][k-1]; }}int lca(int u,int v){ int maxn=log(n)/log(2)+1; if(dep[u] >i)&1) u=fathers[u][i]; if(u==v) return u; for(int i=maxn;i>=0;i--) { if(fathers[u][i]!=fathers[v][i]){ u=fathers[u][i]; v=fathers[v][i]; } } return fathers[u][0];}int main(){ int t,m; sc(t); while(t--) { tot=0; mem(g,0); sc(n); int ans=0; for(int i=1;i