【-32】575B.Bribes[tarjan,LCA]

题目描述

Ruritania is a country with a very badly maintained road network, which is not exactly good news for lorry drivers that constantly have to do deliveries. In fact, when roads are maintained, they become one-way. It turns out that it is sometimes impossible to get from one town to another in a legal way – however, we know that all towns are reachable, though illegally!

Fortunately for us, the police tend to be very corrupt and they will allow a lorry driver to break the rules and drive in the wrong direction provided they receive ‘a small gift’. There is one patrol car for every road and they will request 1000 Ruritanian dinars when a driver drives in the wrong direction. However, being greedy, every time a patrol car notices the same driver breaking the rule, they will charge double the amount of money they requested the previous time on that particular road.

Borna is a lorry driver that managed to figure out this bribing pattern. As part of his job, he has to make $K$ stops in some towns all over Ruritania and he has to make these stops in a certain order. There are $N$ towns (enumerated from $1$ to $N$) in Ruritania and Borna’s initial location is the capital city i.e. town 1. He happens to know which ones out of the $N$ $-$ $1$ roads in Ruritania are currently unidirectional, but he is unable to compute the least amount of money he needs to prepare for bribing the police. Help Borna by providing him with an answer and you will be richly rewarded.

输入输出格式

输入格式

The first line contains $N$, the number of towns in Ruritania. The following $N$ - 1 lines contain information regarding individual roads between towns. A road is represented by a tuple of integers ($a$,$b$,$x$), which are separated with a single whitespace character. The numbers $a$ and $b$represent the cities connected by this particular road, and x is either 0 or 1: 0 means that the road is bidirectional, 1 means that only the $a$ → $b$ direction is legal. The next line contains $K$, the number of stops Borna has to make. The final line of input contains K positive integers $s$1, …, $S_k$: the towns Borna has to visit.

  • $1 ≤ N ≤ 10^5$
  • $1 ≤ K ≤ 10^6$
  • $1 ≤ a, b ≤ N$ for all roads
  • $x∈{0,1}$ for all roads
  • $1 ≤ s_i ≤ N$ for all $1 ≤ i ≤ K$

输出格式

The output should contain a single number: the least amount of thousands of Ruritanian dinars Borna should allocate for bribes, modulo $10^9 + 7$.

输入输出样例

输入样例

1
2
3
4
5
6
7
5
1 2 0
2 3 0
5 1 1
3 4 1
5
5 4 5 2 2

输出样例

1
4

说明

Borna first takes the route $1 → 5$ and has to pay $1000$ dinars. After that, he takes the route $5 → 1 → 2 → 3 → 4$ and pays nothing this time. However, when he has to return via $4 → 3 → 2 → 1 → 5$ , he needs to prepare $3000$ $(1000+2000)$ dinars. Afterwards, getting to 2 via $5 → 1 → 2$ will cost him nothing. Finally, he doesn’t even have to leave town 2 to get to 2, so there is no need to prepare any additional bribe money. Hence he has to prepare $4000$ dinars in total.

题解

开始成功的理解错题意了
以为在一条路径上,第一次经过反向边罚款为1,第二次经过反向边罚款为2

后面wa了几次之后才知道是第一次经过某条反向边罚款为1,第二次经过那条反向边罚款为2.

开始并不知道如何(比较巧妙的)给某条路径上的所有点打标记.然后看了absi的代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=100110;
const int maxm=1000110;
const long long mod=1e9+7;
int n,m,X,Y,Z,id,id1,SS,S2;//SS:标记起点

int to[maxn*2],ne[maxn*2],w[maxn*2],po[maxn];
int to1[maxm*2],ne1[maxm*2],bj[maxm*2],po1[maxm];
int flag[maxm*2];
int vis[maxn];

int down[maxn];//从上往下走每个点的出现次数
int up[maxn];//从下往上走每个点的出现次数
int fa[maxn];
int father[maxn][3];

long long sum;
long long er[maxm];
void add(int x,int y,int z)//加边
{
id++;
to[id]=y;w[id]=z;ne[id]=po[x];po[x]=id;
}
void add1(int x,int y,int z)//询问加边
{
id1++;
to1[id1]=y;
ne1[id1]=po1[x];
bj[id1]=z;//z=0:x->y z=1:y->x
po1[x]=id1;
}
int gf(int x)
{
if (fa[x]==x) return x;
fa[x]=gf(fa[x]);
return fa[x];
}
void hb(int x,int y)//y加入到x所在的集合
{
x=gf(x);
y=gf(y);
fa[y]=x;
}
void dfs(int x,int Fa)
{
vis[x]=1;
for (int i=po[x];i;i=ne[i])
{
int y=to[i];
if (vis[y]) continue;//y扫过了
father[y][0]=x;//标记y的父亲为x
if (w[i]==1) father[y][1]=1;//顺手判一下从x->y方向要不要罚款 down
if (w[i^1]==1) father[y][2]=1;//y->x方向走要不要罚款 up
dfs(y,x);
hb(x,y);
}
for (int i=po1[x];i;i=ne1[i])
{
int y=to1[i];
if (vis[y])
{
if (flag[i]||flag[i^1]) continue;
flag[i]=1;//标记
flag[i^1]=1;//标记
int f3=gf(y);
if (bj[i]==0)//该询问是x->y
{
up[x]++; //x->lca
down[y]++; //lca->y
up[f3]--; //lca->root
down[f3]--;//root->lca
} else
{
up[y]++;//标记
down[x]++;//同上
up[f3]--;//这一句和下一句是防止算多
down[f3]--;
}
}
}
}
void dfs1(int x)
{
if (vis[x]) return;
vis[x]=1;
for (int i=po[x];i;i=ne[i])
{
if (to[i]==father[x][0]) continue;
dfs1(to[i]);
up[x]+=up[to[i]];//更新点x和其父亲连的边的出现次数
down[x]+=down[to[i]];//更新其父亲和x连的边的出现次数
}
}
int main()
{
n=read();
id=1;id1=1;
for (int i=1;i<n;i++)
{
fa[i]=i;
X=read();Y=read();Z=read();
add(X,Y,0);add(Y,X,Z);//加边
}
fa[n]=n;
m=read();
SS=1;
for (int i=1;i<=m;i++)
{
S2=read();
if (S2==SS) continue;
add1(SS,S2,0);//X->Y
add1(S2,SS,1);//Y->X,把询问加进去
SS=S2;
}qingkong
er[0]=1;
for (int i=1;i<=m;i++) er[i]=(er[i-1]+er[i-1])%mod;//预处理2^i(0<=i<=m)
//开始只预处理到了n然后就wa了
dfs(1,-1);//求解
memset(vis,0,sizeof(vis));//标记数组清空
dfs1(1);
sum=0;
for (int i=1;i<=n;i++)
{
sum=sum+er[father[i][1]*(long long)down[i]]-1;//如果i和其父亲连的边边权不为1不会影响结果
sum=sum+er[father[i][2]*(long long)up[i]]-1;
sum%=mod;
}
printf("%I64d",sum);//输出
return 0;
}