昨天吐槽还没A,今天就A了 有个变量开成了全局变量,应该携程局部变量
对于中间的solve我也不懂为什么是nlog2n,我不看题解也不会做
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 2000000000; const int MAXN = 4e5+5; int ans; int co[MAXN]; int vis[MAXN]; struct Pode{ int to,nx, di; Pode(int a=0,int b=0,int c=0):to(a), nx(b), di(c){} }E[MAXN]; int head[MAXN], cot; void add(int u, int v, int w) { E[cot] = Pode(v,head[u],w); head[u] = cot++; } int N,K,M; /***************WeightRoot************/ int all, num, center; int dp[MAXN], nodes[MAXN]; void findRoot(int x,int pre) { nodes[x] = 1; dp[x] = 0; for(int i = head[x]; ~i; i = E[i].nx) { int y = E[i].to; if(y == pre || vis[y]) continue; findRoot(y,x); nodes[x] += nodes[y]; dp[x] = max(dp[x], nodes[y]); } dp[x] = max(dp[x], all-nodes[x]); if(dp[x] < num) { num = dp[x]; center = x; } } int getRoot(int root,int sn) { num = INF; all = sn; center = root; findRoot(root, -1); return center; } /*************treecdq***************/ struct Node{ int dep, v, di; }so[MAXN]; int cmp(Node a,Node b) { return a.dep < b.dep; } int dep[MAXN]; // max dep (black) int g[MAXN]; int mg[MAXN]; void getdep(int x,int pre) { dep[x] = co[x]; int res = 0; for(int i = head[x]; ~i; i = E[i].nx) { int y = E[i].to; if(y == pre || vis[y]) continue; getdep(y,x); res = max(res, dep[y]); } dep[x] += res; } void getg(int x,int pre,int d,int c) { g[c] = max(g[c], d); for(int i = head[x]; ~i; i = E[i].nx) { int y = E[i].to; if(y == pre || vis[y]) continue; getg(y,x,d+E[i].di, c+co[y]); } } void work(int x) { vis[x] = 1; int tot = 0; for(int i = head[x]; ~i; i = E[i].nx) { int y = E[i].to; if(vis[y]) continue; work(getRoot(y,nodes[y])); } for(int i = head[x]; ~i; i = E[i].nx) { int y = E[i].to; if(vis[y]) continue; getdep(y, x); so[++tot].dep = dep[y]; so[tot].v = y; so[tot].di = E[i].di; } sort(so+1,so+tot+1,cmp); // printf("%d:",x); for(int i = 1; i <= tot; ++i) printf("%d ",so[i].dep); printf("\n"); for(int i = 0; i <= so[tot].dep; ++i) mg[i] = -INF; for(int i = 1; i <= tot; ++i) { int t1 = so[i].dep; int t2 = so[i].v; int t3 = so[i].di; for(int j = 0; j <= t1; ++j) g[j] = -INF; getg(t2,x,t3,co[t2]); if(i != 1) { for(int j = 0; j <= K-co[x] && j <= t1; ++j) { int tt = min(so[i-1].dep, K-co[x]-j); if(mg[tt] == -INF) break; if(g[j] != -INF) ans = max(ans, mg[tt]+g[j]); } } for(int j = 0; j <= t1; ++j) { mg[j] = max(g[j], mg[j]); if(j) mg[j] = max(mg[j], mg[j-1]); if(j+co[x] <= K) ans=max(ans, mg[j]); } } vis[x] = 0; } int main(){ while(~scanf("%d %d %d",&N,&K,&M)) { ans = 0; memset(head,-1,sizeof(head)); cot = 0; memset(co,0,sizeof(co)); memset(vis,0,sizeof(vis)); for(int i = 1; i <= M; ++i) { int a; scanf("%d",&a); co[a] ++; } for(int i = 1; i < N; ++i) { int a,b,c; scanf("%d %d %d",&a,&b,&c); add(a,b,c); add(b,a,c); } work(getRoot(1,N)); printf("%d\n",ans); } return 0; }转载于:https://www.cnblogs.com/Basasuya/p/8433726.html