题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2286
数据生成器：http://paste.ubuntu.com/23372796/
就是把虚树建出来了以后，在虚树上跑树上DP
DP很好想，只需要会建虚树就可以辣！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int SGZ = 18;
const int M = 500000+9;
const int N = 250000+9;
const int INF = 0x7fffffff;
int head[N],nxt[M],to[M],cost[M],dep[N],fa[N][SGZ],MN[N][SGZ];
int n,m,p[N],num[N],stk[N],top,tot,T;
bool vis[N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void Add_Edge(int u, int v) {
to[++T] = v; nxt[T] = head[u]; head[u] = T;
}
inline void Add_Edge(int u, int v, int w) {
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}
void DFS(int w, int f) {
static int dfs_cnt = 0; num[w] = ++dfs_cnt;
fa[w][0] = f; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
DFS(to[i], w);
MN[to[i]][0] = cost[i];
}
}
}
inline bool CMP(const int &x, const int &y) {
return num[x] < num[y];
}
inline int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i=17;~i;i--) {
if (dep[fa[x][i]] >= dep[y]) {
x = fa[x][i];
}
}
if (x == y) return x;
for (int i=17;~i;i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
inline int Get_Cost(int w, int pur) {
int ret = INF; pur = dep[pur];
for (int i=17;~i;i--) {
if (dep[fa[w][i]] >= pur) {
ret = min(ret, MN[w][i]);
w = fa[w][i];
}
}
return ret;
}
inline void build() {
stk[top = 1] = 1;
for (int i=1,w,lca;i<=m;i++) {
w = p[i]; lca = LCA(stk[top], w);
while (dep[stk[top]] > dep[lca]) {
if (dep[stk[top-1]] <= dep[lca])
Add_Edge(lca, stk[top]);
else
Add_Edge(stk[top-1], stk[top]);
--top;
}
if (stk[top] != lca) stk[++top] = lca, p[++tot] = lca;
stk[++top] = w;
}
for (int i=1;i<top;i++)
Add_Edge(stk[i], stk[i+1]);
}
inline LL DP(int w, int f) {
LL tmp = 0;
for (int i=head[w];i;i=nxt[i])
tmp += DP(to[i], w);
if (vis[w]) return Get_Cost(w, f);
else if (w != 1) return min((LL)Get_Cost(w, f), tmp);
else return tmp;
}
int main() {
n = read();
for (int i=1,u,v;i<n;i++) {
u = read(); v = read();
Add_Edge(u, v, read());
}
DFS(1, 1); MN[1][0] = INF;
for (int j=1;j<=17;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
MN[i][j] = min(MN[i][j-1], MN[fa[i][j-1]][j-1]);
}
}
memset(head,0,sizeof(head));
for (int k=read();k;k--) {
m = tot = read(); T = 0;
for (int i=1;i<=m;i++) vis[p[i] = read()] = 1;
sort(p+1, p+1+m, CMP);
build();
printf("%lld\n",DP(1,1)); head[1] = 0;
for (int i=1;i<=tot;i++) vis[p[i]] = 0, head[p[i]] = 0;
}
return 0;
}
I’m not sure where you’re getting your information, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for great info I was looking for this info for my mission.
Wow, this paragraph is pleasant, my sister is analyzing these kinds of things,
so I am going to convey her.
This is really fascinating, You’re an overly professional blogger.
I’ve joined your feed and look forward to searching for extra of your excellent post.
Also, I have shared your website in my social networks
What i do not realize is actually how you are now not
really a lot more neatly-appreciated than you may be now. You’re very intelligent.
You already know thus significantly in the case of this matter, produced me in my
opinion imagine it from a lot of various angles. Its like men and women aren’t
involved until it’s one thing to accomplish with Woman gaga!
Your individual stuffs great. At all times handle it
up!
There is definately a lot to know about this issue.
I like all of the points you have made.
Hi to every , as I am in fact eager of reading this website’s post to be updated on a regular basis.
It consists of nice information.
Today, while I was at work, my sister stole my iPad
and tested to see if it can survive a 25 foot drop, just so she can be a youtube sensation. My iPad
is now broken and she has 83 views. I know this is entirely off topic but
I had to share it with someone!
Wow that was strange. I just wrote an really long comment but after I clicked submit my comment didn’t show up.
Grrrr… well I’m not writing all that over again.
Regardless, just wanted to say great blog!
Hey just wanted to give you a brief heads up and let you know a few of the images aren’t loading correctly.
I’m not sure why but I think its a linking issue. I’ve tried it in two different web browsers and
both show the same results.
Keep on working, great job!
Hey there! I simply want to offer you a big thumbs up for the excellent information you’ve got right here on this post.
I am returning to your site for more soon.
I’m not sure where you are getting your information, but great topic.
I needs to spend some time learning much more or understanding more.
Thanks for fantastic information I was looking for this information for
my mission.
Today, I went to the beach with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to
her ear and screamed. There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is completely off topic but I had to tell someone!
I needed to post you one tiny observation to be able to give thanks yet again for the extraordinary opinions you’ve shown above. It has been simply surprisingly open-handed with you to convey unhampered what exactly a number of people could have marketed for an ebook to make some dough for themselves, certainly since you might well have done it in case you wanted. These inspiring ideas additionally served like a great way to understand that someone else have a similar keenness like my very own to learn great deal more on the topic of this condition. I think there are lots of more pleasurable situations in the future for individuals who check out your blog.
Touche. Sound arguments. Keep up the great effort.
I used to be suggested this blog by my cousin. I am not sure whether this post is written through him as no one else understand such detailed approximately my
trouble. You’re incredible! Thank you!
Someone necessarily help to make severely posts I might state.
That is the very first time I frequented your web page and so far?
I amazed with the research you made to create this actual publish incredible.
Great task!
I love reading through an article that will make people think.
Also, many thanks for allowing for me to comment!
Greetings I am so thrilled I found your weblog,
I really found you by error, while I was browsing on Aol for something else, Nonetheless I am here now and would just like to say thanks for a fantastic post
and a all round entertaining blog (I also love the theme/design), I don’t have time to read it all at the minute
but I have saved it and also added your RSS feeds, so when I have time I will be back to read more, Please do keep up the
superb job.
What’s up to every , as I am in fact eager of
reading this blog’s post to be updated on a regular basis.
It contains nice material.
Valuable information. Lucky me I discovered your site by accident,
and I am surprised why this accident did not took place earlier!
I bookmarked it.
Rattling good visual appeal on this site, I’d rate it 10 10.