注意到一个人的三条链一定不会同时选（忽略仅选一个终点的限制），因为其有公共点（起点）
换言之，问题相当于给定$3m$条链，选择$m$条没有公共点的链，并最小化代价和
进一步的，显然也不存在多于$m$条且没有公共点的链，因此”选择$m$条链”也可以理解为选尽量多的链（若选不到$m$条链即为-1）的同时最小化代价和
更进一步的，只需要将每一条链的代价从$c$变为$C-c$（其中$C$为足够大量，可以设为$10^{12}$），即可忽略”选尽量多的链”的条件（注意代价取了相反数）
综上，问题即相当于给定$3m$条链，选择若干条没有公共点的链，并最大化代价和
设最终答案为$ans$，若$ansle (m-1)C$答案为-1，否则答案为$mC-ans$
对于这个问题，考虑其对偶问题：给每一个点一个非负整数的权值，要求每一条链上所有点的权值和不小于该链的代价，求最小的权值和
两者的答案是相同的，证明如下——
假设最小的权值和为$sum$，由于一条链的权值小于等于该链上所有点权值和，那么对于一种选链的方案，权值总和即小于等于所有经过的点权值和，注意到没有重复点且权值非负，即得到$ansle sum$
另一方面，考虑贪心的构造这个最小的权值和，即从底向上依次选择权值，使得以其为lca的路径都满足条件且最小（若不存在路径或都已经满足则设为0）
此时，不断找到最浅的且未被经过的节点，若该点边权为0则跳过，否则必然恰有一条以其为lca且权值和恰等于路径上边权和的链，选择其并重复此过程，最终不难得到$ansge sum$
综上，有$ans=sum$，即得证
从证明过程中，也得到了该问题的贪心做法，其的维护即要支持单点修改+链查询，再通过差分转换为子树修改+单点查询，并使用树状数组维护即可
时间复杂度为$o(nlog n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define ll long long 5 struct Edge{ 6 int nex,to; 7 }edge[N<<1]; 8 struct Data{ 9 int x,y; 10 ll z; 11 }; 12 vector<Data>v[N]; 13 int E,t,n,m,x,y,head[N],dfn[N],sz[N],dep[N],fa[N][21]; 14 ll C=1e12,z,ans,f[N]; 15 void add(int x,int y){ 16 edge[E].nex=head[x]; 17 edge[E].to=y; 18 head[x]=E++; 19 } 20 int lca(int x,int y){ 21 if (dep[x]<dep[y])swap(x,y); 22 for(int i=20;i>=0;i--) 23 if (dep[fa[x][i]]>=dep[y])x=fa[x][i]; 24 if (x==y)return x; 25 for(int i=20;i>=0;i--) 26 if (fa[x][i]!=fa[y][i]){ 27 x=fa[x][i]; 28 y=fa[y][i]; 29 } 30 return fa[x][0]; 31 } 32 void dfs(int k,int f,int s){ 33 dfn[k]=++dfn[0]; 34 sz[k]=1; 35 dep[k]=s; 36 fa[k][0]=f; 37 for(int i=1;i<=20;i++)fa[k][i]=fa[fa[k][i-1]][i-1]; 38 for(int i=head[k];i!=-1;i=edge[i].nex) 39 if (edge[i].to!=f){ 40 dfs(edge[i].to,k,s+1); 41 sz[k]+=sz[edge[i].to]; 42 } 43 } 44 int lowbit(int k){ 45 return (k&(-k)); 46 } 47 void update(int k,ll x){ 48 while (k<=n){ 49 f[k]+=x; 50 k+=lowbit(k); 51 } 52 } 53 ll query(int k){ 54 ll ans=0; 55 while (k){ 56 ans+=f[k]; 57 k-=lowbit(k); 58 } 59 return ans; 60 } 61 void calc(int k,int fa){ 62 for(int i=head[k];i!=-1;i=edge[i].nex) 63 if (edge[i].to!=fa)calc(edge[i].to,k); 64 ll s=0; 65 for(int i=0;i<v[k].size();i++){ 66 x=v[k][i].x,y=v[k][i].y,z=v[k][i].z; 67 s=max(s,z-(query(dfn[x])+query(dfn[y])-2*query(dfn[k]))); 68 } 69 update(dfn[k],s); 70 update(dfn[k]+sz[k],-s); 71 ans+=s; 72 } 73 int main(){ 74 scanf("%d",&t); 75 while (t--){ 76 scanf("%d%d",&n,&m); 77 E=ans=dfn[0]=0; 78 for(int i=1;i<=n;i++){ 79 head[i]=-1,f[i]=0; 80 v[i].clear(); 81 } 82 for(int i=1;i<n;i++){ 83 scanf("%d%d",&x,&y); 84 add(x,y); 85 add(y,x); 86 } 87 dfs(1,1,0); 88 for(int i=1;i<=m;i++){ 89 scanf("%d",&x); 90 for(int j=1;j<=3;j++){ 91 scanf("%d%lld",&y,&z); 92 v[lca(x,y)].push_back(Data{x,y,C-z}); 93 } 94 } 95 calc(1,0); 96 if (ans<=C*(m-1))printf("-1 "); 97 else printf("%lld ",C*m-ans); 98 } 99 return 0; 100 }
View Code
Se você está pensando em usar um aplicativo espião de celular, então você fez a escolha certa.
Quando tiver dúvidas sobre as atividades de seus filhos ou a segurança de seus pais, você pode hackear seus telefones Android em seu computador ou dispositivo móvel para garantir a segurança deles. Ninguém pode monitorar o tempo todo, mas há um software espião profissional que pode monitorar secretamente as atividades dos telefones Android sem alertá-los.