T1
毒瘤计数题，至少想假了 (5) 次。
不难发现，(d) 不管是奇数还是偶数，都有一个中心点，我们考虑如果 (d) 为偶数，那么中心就是一个点，否则及时一条边，不难发现中间为一条边是好做的，我们直接预处理回答询问即可。至于偶数，我们可以遍历其邻点，然后对于哪些点我们枚举所有组合方式，减去不合法的即可。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 4010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
struct edge{
int from,to,next;
inline void Init(int fr_,int to_,int ne_){
from=fr_;to=to_;next=ne_;
}
}li[N<<1];
int head[N],tail=1;
inline void Add(int from,int to){
li[++tail].Init(from,to,head[from]);
head[from]=tail;
}
int d[N][N][2],Dep[N],sum[N][N][2],Root,n,m,Tag,TwoPow[N];
inline int ksm(int a,int b,int mod){
int res=1;while(b){if(b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline void dfs(int k,int fa,int op){
Dep[k]=Dep[fa]+1;d[Root][Dep[k]][op]++;
for(int x=head[k];x;x=li[x].next){
int to=li[x].to;
if(Tag==x||(Tag^1)==x) continue;
if(to==fa) continue;
dfs(to,k,op);
}
}
inline void Init(){
read(n);
for(int i=1;i<=n-1;i++){
int from,to;read(from);read(to);
Add(from,to);Add(to,from);
}
Dep[0]=-1;
for(int i=2;i<=tail;i++){
Tag=i;Root=i;dfs(li[i].from,0,0);dfs(li[i].to,0,1);
sum[i][0][0]=d[i][0][0];sum[i][0][1]=d[i][0][1];
for(int j=1;j<=n;j++){
sum[i][j][0]=sum[i][j-1][0]+d[i][j][0];
sum[i][j][1]=sum[i][j-1][1]+d[i][j][1];
}
// printf("li[%d].from=%d li[%d].to=%d
",i,li[i].from,i,li[i].to);
// for(int j=1;j<=n;j++){
// printf("d[%d][%d][0]=%d d[%d][%d][1]=%d
",i,j,d[i][j][0],i,j,d[i][j][1]);
// }
}
TwoPow[0]=1;
for(int i=1;i<=n;i++) TwoPow[i]=1ll*TwoPow[i-1]*2%mod;
}
inline void Solve(){
read(m);
for(int i=1;i<=m;i++){
int di;read(di);
int Ans=0;
if(di&1){
int len=di/2;
for(int j=2;j<=tail;j+=2){
int n1=d[j][len][0];
int n2=d[j][len][1];
int m=0;
if(len>=1) (m+=sum[j][len-1][0]+sum[j][len-1][1])%=mod;
Ans=(Ans+1ll*(TwoPow[n1]-1)*(TwoPow[n2]-1)%mod*TwoPow[m])%mod;
}
}
else{
for(int i=1;i<=n;i++){
int sum1=0,sum2=1;
for(int x=head[i];x;x=li[x].next){
// sum1=(sum1+d[x][di/2-1][1]);
if(di/2>=2) sum2=(sum2+sum[x][di/2-2][1])%mod;
}
int now=1;
for(int x=head[i];x;x=li[x].next){
// now=(now+1ll*(sum1-d[x][di/2-1][1])*d[x][di/2-1][1]%mod)%mod;
// now=1ll*now*(d[x][di/2-1][1]+1);
now=1ll*now*((TwoPow[d[x][di/2-1][1]]-1)+1)%mod;
(sum1+=(TwoPow[d[x][di/2-1][1]]-1))%=mod;
}
now--;now-=sum1;
Ans=(Ans+1ll*now*TwoPow[sum2]%mod)%mod;
}
}
printf("%d
",(Ans%mod+mod)%mod);
}
}
signed main(){
freopen("my.in","r",stdin);
freopen("my.out","w",stdout);
Init();Solve();
return 0;
}
T2
二分图博弈学习笔记例题 3。
链接
T3
这个题正解是用树上被增法，然而因为数据过水，所以暴力可做。据说出题人是随机建树。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 500010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T> inline T Max(T a,T b){return a<b?b:a;}
int n,m,tot;
map<int,int> Map[N];
vector<int> v[N],col[N];
int From[N],To[N],Fa[N][32],Dep[N];
inline void Dfs(int k,int f){
Dep[k]=Dep[f]+1;Fa[k][0]=f;
for(int i=1;i<=30;i++) Fa[k][i]=Fa[Fa[k][i-1]][i-1];
for(int to:v[k]){if(to==f) continue;Dfs(to,k);}
}
inline int GetLca(int a,int b){
if(Dep[a]<Dep[b]) swap(a,b);
for(int i=30;i>=0;i--) if(Dep[Fa[a][i]]>=Dep[b]) a=Fa[a][i];
if(a==b) return a;
for(int i=30;i>=0;i--) if(Fa[a][i]!=Fa[b][i]){a=Fa[a][i];b=Fa[b][i];}return Fa[a][0];
}
inline void Init(){
read(n);read(m);
for(int i=1;i<=m;i++){
int from,to,w;read(from);read(to);read(w);
if(!Map[from][to]){
Map[from][to]=++tot;Map[to][from]=tot;
v[from].push_back(to);v[to].push_back(from);
From[tot]=from;To[tot]=to;
col[tot].push_back(w);
}
else col[Map[from][to]].push_back(w);
}
Dfs(1,0);
}
inline void Solve(int a,int b){
int Lca=GetLca(a,b);
// printf("Lca=%d
",Lca);
vector<int> Road,c;Road.clear();
int k=a;while(k!=Lca){Road.push_back(k);k=Fa[k][0];}
Road.push_back(Lca);c.clear();
k=b;while(k!=Lca){c.push_back(k);k=Fa[k][0];}
for(int i=c.size()-1;i>=0;i--) Road.push_back(c[i]);
priority_queue<pair<int,int> > q[2];
q[0].push(make_pair(0,0));int o=0;
// for(int i=0;i<Road.size();i++) printf("%d ",Road[i]);
// puts("");
for(int i=0;i<Road.size()-1;i++){
// printf("i=%d
",i);
o^=1;int now=Map[Road[i]][Road[i+1]];
while(q[o].size()) q[o].pop();
for(int co:col[now]){
pair<int,int> Top=q[o^1].top();
if(co!=Top.second){q[o].push(make_pair(Top.first+1,co));}
else{
q[o^1].pop();
if(q[o^1].size()){
q[o].push(make_pair(Max(Top.first,q[o^1].top().first+1),co));
}
else q[o].push(make_pair(Top.first,co));
q[o^1].push(Top);
}
}
}
printf("%d
",Max(0,q[o].top().first-1));
}
int q;
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
Init();
read(q);
while(q--){
int a,b;read(a);read(b);
Solve(a,b);
}
return 0;
}