比赛链接：https://codeforces.com/group/2g1PZcsgml/contest/337661
A，D，K，3/12，第11名，还好。
A他们挺快写出来了。D我感觉可以用上一场A一样的做法，成功。G用AC自动机把K过了；字符串的板子我还都老生疏了，真惭愧。其他题看来看去都没有成熟的思路，直到比赛结束。G最后十五分钟用分治猛改J题，可惜太匆忙，WA了；后来改改就A了。
话说那个教室空调好冷啊。
题意：
给定一颗树和树上的若干条路径（的两个端点），求最小的点集，使得每条路径至少有一个点在此点集中。\( 1 \leq n , m \leq 10^5 \) 。
分析：
树上的路径比较特殊，一般要关注LCA，这题也是。一个很好的发现是两条路径如果相交，那么较低路径上的LCA一定是交点之一。所以答案一定从LCA中选。就可以贪心，从低往高找LCA，用找到的LCA覆盖尽量多的路径。
但怎么实现还是个问题；这里可以用set，用法好妙啊。给每个点开一个set，一开始存的是以这个点为端点的路径的编号。然后dfs，把子节点的set启发式合并到父节点的set里；如果合并过程中发现有相同的元素，说明这个父节点是个LCA（两端点在此会师），那么答案++，set全清空，意思是这些路径都被覆盖了。可以想到，如果一条路径在其某一侧被覆盖了，两端点中那一侧的那个的set里一开始存的路径编号就被清空了，那么在LCA处也不会会师，也就不再算答案了。复杂度是 \( O(nlog^2(n)) \) 的。
代码如下：
#include<iostream>
#include<set>
using namespace std;
int const N=1e5+5;
int n,m,hd[N],to[N<<1],nxt[N<<1],cnt,id[N],ans;
bool is[N];
set<int>st[N];
int rd()
{
int ret=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret*f;
}
void add(int x,int y){nxt[++cnt]=hd[x]; hd[x]=cnt; to[cnt]=y;}
int mer(int x,int y)
{
if(st[x].size()<st[y].size())swap(x,y);
for(int it:st[y])
{
if(st[x].find(it)!=st[x].end())return -1;
st[x].insert(it);
}
return x;
}
void dfs(int u,int fa)
{
if(is[u])ans++,st[id[u]].clear();//
for(int i=hd[u],v;i;i=nxt[i])
{
if((v=to[i])==fa)continue;
dfs(v,u);
if(is[u]){st[v].clear(); continue;}//前面已经决定选u了
int k=mer(id[u],id[v]);
if(k==-1)st[id[u]].clear(),st[id[v]].clear(),is[u]=1,ans++;
else id[u]=k;
}
}
int main()
{
n=rd();
for(int i=1,x,y;i<n;i++)
x=rd(),y=rd(),add(x,y),add(y,x);
for(int i=1;i<=n;i++)id[i]=i;
m=rd();
for(int i=1,x,y;i<=m;i++)
{
x=rd(); y=rd();
if(x==y)is[x]=1;
else st[x].insert(i),st[y].insert(i);
}
dfs(1,0);
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(is[i])printf("%d ",i);
printf("\n");
return 0;
}
me
题意：
给定一张图，可求1号点到每个点的最短路，问单独增大每条边，有多少点的最短路会受到影响？\( 2 \leq n \leq 2*10^5 , n-1 \leq m \leq 2*10^5 \) 。
分析：
支配树？
先dijkstra求出最短路；过程中每个点用vector存下相同的最短路，存最后那条边即可。然后这些最短路就形成了一个拓扑图。
这时我们需要从这个图中提取出一棵树，使得一条边下的子树的所有点都会被这条边影响。想想可以发现，对于一个点，所有最短路上的前一个点（下称前驱点）在图中的拓扑序比它靠前；如果我们按照拓扑序构造那棵树，那么那些前驱点会在当前点之前加入树中。而对于这个点，可以影响到它最短路的边就是这些路共有的部分，也就是树上LCA往上的部分。
所以我们找到所有前驱点在已有的树上的LCA，然后把当前点直接连在LCA下面，这个树就还满足我们的需求。
这样做完以后得到一棵树，然后dfs求子树大小就可以得到边影响的点数了。这还需要我们在造树的过程中时刻记录边的编号。
代码如下：
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define ll long long
using namespace std;
int const N=2e5+5;
int n,m,hd[N],to[N<<1],fr[N<<1],nxt[N<<1],cnt=1;//cnt=1
int du[N],f[N][25],dep[N],tag[N],ans[N],siz[N];
ll D[N],w[N<<1];//ll!
bool vis[N];
vector<int>ve[N],E[N],tr[N];
struct Nd{
ll dis,id;
bool operator < (const Nd &a) const
{return dis>a.dis;}
};
priority_queue<Nd>q;
queue<int>tq;
void add(int x,int y,int s){nxt[++cnt]=hd[x]; hd[x]=cnt; to[cnt]=y; fr[cnt]=x; w[cnt]=s;}
void dij()
{
q.push((Nd){0,1});
memset(D,0x3f3f,sizeof D); D[1]=0;
while(q.size())
{
int u=q.top().id; q.pop();
if(vis[u])continue; vis[u]=1;
for(int i=hd[u],v;i;i=nxt[i])
{
if(vis[v=to[i]])continue;
if(D[v]>D[u]+w[i])
{
ve[v].clear(); ve[v].push_back(i); du[v]=1;//ve:拓扑图上指来的边
D[v]=D[u]+w[i];
q.push((Nd){D[v],v});
}
else if(D[v]==D[u]+w[i])ve[v].push_back(i),du[v]++;
}
}
for(int i=1;i<=n;i++)
for(int it:ve[i])E[fr[it]].push_back(it);//E:拓扑图上指出的边
//for(int i=1;i<=n;i++)printf("du[%d]=%d\n",i,du[i]);
}
int getlca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)
if(f[x][i]&&dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
void topo()
{
tq.push(1);
while(tq.size())
{
int u=tq.front(); tq.pop();
for(int e:E[u])
{
int v=to[e]; du[v]--;
//printf("%d-%d\n",u,v);
if(!du[v])tq.push(v);
else continue;
if(ve[v].size()==1)
{
f[v][0]=u; dep[v]=dep[u]+1;
tag[v]=e/2;//边的编号/2
//printf("u=%d tag[%d]=%d\n",u,v,tag[v]);
tr[u].push_back(v);//tr:最短路树上指向的点
}
else
{
int lca=fr[ve[v][0]],sz=ve[v].size();
for(int i=1;i<sz;i++)
lca=getlca(lca,fr[ve[v][i]]);//所有最短路的lca
f[v][0]=lca; dep[v]=dep[lca]+1;
tr[lca].push_back(v);
}
for(int i=1;i<=20;i++)
f[v][i]=f[f[v][i-1]][i-1];
}
}
}
void dfs(int u)
{
siz[u]=1;
for(int v:tr[u]){dfs(v); siz[u]+=siz[v];}
if(tag[u])ans[tag[u]]=siz[u];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x,y,s;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&s);
add(x,y,s); add(y,x,s);
}
dij(); topo(); dfs(1);
//for(int i=1;i<=n;i++)printf("tag[%d]=%d\n",i,tag[i]);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
me