题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3047
这题应该是基环树？然而不会基环树的做法QAQ
所以我们把他当成仙人掌来做吧！ (*^_^*)
#include<iostream>
#include<cstdio>
#include<vector>
#define abs(x) ((x)<0?-(x):(x))
using namespace std;
const int MAXN = 40000;
int n,m,q,nxt[MAXN],to[MAXN],head[MAXN],que[MAXN];
int fa[MAXN][20],num[MAXN],lowlink[MAXN],ring_cnt,ring_num[MAXN];
int ori[MAXN],dep[MAXN],dis[MAXN],cost[MAXN],length[MAXN];
vector<int> rings[MAXN];
inline int read(){
char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}
inline void AddEdge(int u, int v, int c){
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = c;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = c;
}
void DFS(int w, int f){
static int T = 0, tot = 0;
num[w] = lowlink[w] = ++T; que[++tot] = w;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) {
DFS(to[i],w);
if (lowlink[to[i]] > num[w]) tot--;
else if (lowlink[to[i]] < num[w]) lowlink[w] = lowlink[to[i]];
else {
ring_cnt++;
while (que[tot] != w) rings[ring_cnt].push_back(que[tot--]);
rings[ring_cnt].push_back(w);
}
} else lowlink[w] = min(lowlink[w],num[to[i]]);
}
}
inline void prework(){
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size();
int rt = rings[k][sz-1],tmp=0;
for (int i=1;i<=sz;i++) que[i] = rings[k][i-1];
que[0] = rt; que[sz+1] = que[1];
for (int w=1;w<=sz;w++) {
for (int i=head[que[w]];i;i=nxt[i])
if (to[i] == que[w-1]) to[i] = 0, tmp += cost[i];
else if (to[i] == que[w+1]) to[i] = 0;
ori[que[w]] = tmp;
} ori[rt] = 0; length[k] = tmp;
for (int i=1;i<sz;i++) ring_num[que[i]] = k;
for (int i=1;i<sz;i++) AddEdge(rt,que[i],min(ori[que[i]],tmp-ori[que[i]]));
}
}
void GetDis(int w, int f){
fa[w][0] = f; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) if (!dep[to[i]] && to[i])
dis[to[i]] = dis[w] + cost[i], GetDis(to[i],w);
}
inline void LCA_init(){
for (int k=1;k<=18;k++) for (int i=1;i<=n;i++)
fa[i][k] = fa[fa[i][k-1]][k-1];
}
inline int LCA(int a, int b, int &l1, int &l2) {
if (dep[a] < dep[b]) swap(a,b);
for (int k=18;~k;k--) if (dep[fa[a][k]] >= dep[b])
a = fa[a][k];
l1 = l2 = a;
if (a == b) return a;
for (int k=18;~k;k--) if (fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];
l1 = a; l2 = b; return fa[a][0];
}
int main(){
n = read(); m = read(); q = read();
for (int i=1,a,b,c;i<=m;i++) a = read(), b = read(), c = read(), AddEdge(a, b, c);
DFS(1,0); prework(); dep[1] = 1; GetDis(1,0); LCA_init();
for (int i=1,u,v,l1,l2;i<=q;i++){
u = read(), v = read();
int lca = LCA(u, v, l1, l2);
if (ring_num[l1] && ring_num[l1] == ring_num[l2]) {
int len = abs(ori[l1] - ori[l2]);
len = min(length[ring_num[l2]]-len,len);
printf("%d\n",dis[u]+dis[v]-dis[l1]-dis[l2]+len);
} else printf("%d\n",dis[u]+dis[v]-2*dis[lca]);
}
return 0;
}
同样，这份代码的预处理部分仍然是错的
正确的请参见BZOJ_1023
These are really wonderful ideas in on the topic of blogging.
You have touched some fastidious factors here. Any way keep
up wrinting.
I love what you guys tend to be up too. This kind of
clever work and reporting! Keep up the very good works guys I’ve added you guys to my blogroll.
you’re truly a good webmaster. The website loading velocity is amazing.
It kind of feels that you’re doing any distinctive trick.
In addition, The contents are masterpiece.
you’ve performed a magnificent process on this
topic!
It’s remarkable to pay a visit this web site and reading the views
of all mates regarding this post, while I am also eager of getting experience.
Does your website have a contact page? I’m having a tough time locating it but,
I’d like to send you an email. I’ve got some recommendations for your blog you might be interested in hearing.
Either way, great site and I look forward to seeing it expand over time.
Write more, thats all I have to say. Literally,
it seems as though you relied on the video to make your point.
You obviously know what youre talking about, why throw away your intelligence on just posting videos to your site when you could be giving us something enlightening to read?
Hello There. I found your blog using msn. This
is a really well written article. I’ll make sure to bookmark it and come back
to read more of your useful information. Thanks for the post.
I will certainly return.
What’s Happening i am new to this, I stumbled upon this I’ve found It positively helpful and it has helped
me out loads. I hope to give a contribution & aid different users like its helped me.
Good job.
This is the perfect webpage for anyone who wishes to find
out about this topic. You know a whole lot its almost hard to argue
with you (not that I really would want to…HaHa).
You certainly put a fresh spin on a topic that’s been written about for decades.
Wonderful stuff, just wonderful!
I’m really inspired together with your writing abilities as neatly as with the structure in your weblog.
Is this a paid theme or did you modify it yourself?
Either way stay up the excellent high quality writing, it’s rare to peer a nice weblog
like this one these days..
Thanks for sharing your thoughts. I really appreciate your
efforts and I will be waiting for your further post thanks once again.
I am continually searching online for posts that can help me. Thx!
Everything is very open with a precise explanation of the challenges.
It was definitely informative. Your site is useful. Thanks for sharing!
Right now it seems like Drupal is the top blogging platform available
right now. (from what I’ve read) Is that what you’re using on your blog?
It’s the best time to make some plans for the future and it is time to be happy.
I have read this post and if I could I wish to suggest
you few interesting things or suggestions. Perhaps you could write next articles referring
to this article. I wish to read more things about it!
Hey! I’m at work surfing around your blog from my new iphone!
Just wanted to say I love reading your blog and look forward to all
your posts! Carry on the great work!
Hi there, i read your blog from time to time and i
own a similar one and i was just wondering if you get a lot of spam feedback?
If so how do you stop it, any plugin or anything you can recommend?
I get so much lately it’s driving me crazy so
any assistance is very much appreciated.
Sweet blog! I found it while browsing on Yahoo News.
Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but
I never seem to get there! Appreciate it
I’m excited to uncover this website. I wanted to thank you for your time for this particularly fantastic read!!
I definitely appreciated every bit of it and I have you book marked to see new things on your site.
Write more, thats all I have to say. Literally,
it seems as though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence on just posting videos to your blog when you could be giving us something enlightening to read?
Hello there, I discovered your web site by means of Google while
looking for a comparable subject, your web
site got here up, it looks great. I have bookmarked it in my google bookmarks.
Hello there, just become aware of your blog thru Google, and found that
it’s really informative. I am going to be careful for brussels.
I will be grateful should you continue this in future. Lots of other
folks might be benefited from your writing. Cheers!
What’s up i am kavin, its my first occasion to commenting anywhere, when i read this
paragraph i thought i could also create comment due
to this brilliant piece of writing.
I haven¦t checked in here for a while since I thought it was getting boring, but the last several posts are good quality so I guess I¦ll add you back to my daily bloglist. You deserve it my friend 🙂