算法笔记--树的直径 && 树形dp && 虚树 && 树分治 && 树上差分 && 树链剖分
2024-03-26 11:33:34
树的直径：
利用了树的直径的一个性质：距某个点最远的叶子节点一定是树的某一条直径的端点。
先从任意一顶点a出发，bfs找到离它最远的一个叶子顶点b,然后再从b出发bfs找到离b最远的顶点c,那么b和c之间的距离就是树的直径。
用dfs也可以。
模板：
const int N=1e6+;
int head[N];
int dis[N];
bool vis[N];
int cnt=,b,mxn=;
struct edge
{
int to,w,next;
}edge[N];
void add_edge(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void bfs(int s)
{
queue<int>q;
q.push(s);
int now,nxt;
mxn=;
b=s;
mem(dis,);
mem(vis,false);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=head[now];~i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
q.push(edge[i].to);
vis[edge[i].to]=true;
dis[edge[i].to]=dis[now]+edge[i].w;
if(dis[edge[i].to]>mxn)
{
mxn=dis[edge[i].to];
b=edge[i].to;
}
}
}
}
}
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=1e6+;
int head[N];
int dis[N];
bool vis[N];
int cnt=,b,mxn=;
struct edge
{
int to,w,next;
}edge[N];
void add_edge(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void bfs(int s)
{
queue<int>q;
q.push(s);
int now,nxt;
mxn=;
b=s;
mem(dis,);
mem(vis,false);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=head[now];~i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
q.push(edge[i].to);
vis[edge[i].to]=true;
dis[edge[i].to]=dis[now]+edge[i].w;
if(dis[edge[i].to]>mxn)
{
mxn=dis[edge[i].to];
b=edge[i].to;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int u,v,w;
mem(head,-);
//freopen("in.txt","r",stdin);
while(cin>>u>>v>>w)add_edge(u,v,w),add_edge(v,u,w);
bfs();
//cout<<b<<' '<<mxn<<endl;
bfs(b);
cout<<mxn<<endl;
//fclose(stdin);
return ;
}
思路：
先构建一个虚树，最短路程=m*2-mx（m为虚树的边数，mx为虚树直径），起点s两次dfs时每次都找最小的，最后在两个中再取最小。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=;
int head[N];
bool vis[N]={false};
int dis[N];
int s,mx,cnt,sum;
bool belong[N]={false};
struct edge
{
int to,next;
}edge[*N];
void add_edge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int u)
{
vis[u]=true;
for(int i=head[u];~i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
dis[edge[i].to]=dis[u]+;
dfs(edge[i].to);
if(belong[edge[i].to])
{
sum+=;
belong[u]=true;
if(dis[edge[i].to]>mx)
{
mx=dis[edge[i].to];
s=edge[i].to;
}
else if(dis[edge[i].to]==mx)
{
if(edge[i].to<s)
{
s=edge[i].to;
}
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n,m,u,v,t;
mem(head,-);
cnt=;
cin>>n>>m;
for(int i=;i<n-;i++)
{
cin>>u>>v;
add_edge(u,v);
add_edge(v,u);
}
for(int i=;i<m;i++)cin>>t,belong[t]=true;
mx=;
s=t;
dfs(t);
mem(vis,false);
mem(dis,);
sum=;
int tt=s;
dfs(s);
cout<<min(tt,s)<<endl<<sum-mx<<endl;
return ;
}
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=2e5+;
int head[N];
bool vis[N]={false};
int dis[N];
int t,mx,cnt;
struct edge
{
int to,w,next;
}edge[*N];
void add_edge(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void bfs(int s)
{
mem(vis,false);
mem(dis,);
vis[s]=true;
t=s;
mx=;
queue<int>q;
q.push(s);
int now,next;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=head[now];~i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
vis[edge[i].to]=true;
q.push(edge[i].to);
dis[edge[i].to]=dis[now]+edge[i].w;
if(dis[edge[i].to]>mx)
{
mx=dis[edge[i].to];
t=edge[i].to;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n,m,u,v,w;
char c;
cin>>n>>m;
cnt=;
mem(head,-);
while(m--)
{
cin>>u>>v>>w>>c;
add_edge(u,v,w);
add_edge(v,u,w);
}
bfs();
bfs(t);
cout<<mx<<endl;
return ;
}
思路：同树的直径
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=1e3+;
char mp[N][N];
bool vis[N][N];
int n,m,tx,ty,mx;
struct node
{
int x,y,step;
};
int dir[][]={,,,,-,,,-};
void bfs(int x,int y)
{
queue<node>q;
node now,nxt;
now.x=x,now.y=y,now.step=;
q.push(now);
while(!q.empty())
{
now=q.front();
vis[now.x][now.y]=true;
if(now.step>mx)
{
mx=now.step;
tx=now.x;
ty=now.y;
}
q.pop();
for(int i=;i<;i++)
{
nxt.x=now.x+dir[i][];
nxt.y=now.y+dir[i][];
if(<=nxt.x&&nxt.x<n&&<=nxt.y&&nxt.y<m&&mp[nxt.x][nxt.y]=='.'&&!vis[nxt.x][nxt.y])
{
nxt.step=now.step+;
q.push(nxt);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int T;
cin>>T;
while(T--)
{
cin>>m>>n;
for(int i=;i<n;i++)
cin>>mp[i];
mem(vis,false);
mx=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
if(mp[i][j]=='.')
{
bfs(i,j);
break;
}
}
mem(vis,false);
bfs(tx,ty);
cout<<"Maximum rope length is "<<mx<<"."<<endl;
}
return ;
}
树形dp:
思路：http://blog.csdn.net/shuangde800/article/details/9732825
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=1e4+;
int head[N];
ll dis[N][];
bool vis[N];
int cnt;
struct edge
{
int to,w,next;
}edge[N*];
void add_edge(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
ll dfs(int u)
{
vis[u]=true;
for(int i=head[u];~i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
dis[u][]=max(dis[u][],dfs(edge[i].to)+edge[i].w);
}
}
return dis[u][];
}
void DFS(int u)
{
vis[u]=true;
ll mx1=,mx2=;
int v1,v2;
for(int i=head[u];~i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
ll temp=dis[edge[i].to][]+edge[i].w;
if(temp>mx1)
{
mx2=mx1;
v2=v1;
mx1=temp;
v1=edge[i].to;
}
else if(temp==mx1||temp>mx2)
{
mx2=temp;
v2=edge[i].to;
}
}
}
int temp=dis[u][];
if(temp>mx1)
{
mx2=mx1;
v2=v1;
mx1=temp;
v1=-;
}
else if(temp==mx1||temp>mx2)
{
mx2=temp;
v2=-;
}
for(int i=head[u];~i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
if(v1!=edge[i].to)dis[edge[i].to][]=mx1+edge[i].w;
else dis[edge[i].to][]=mx2+edge[i].w;
DFS(edge[i].to);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n,u,v,w;
while(cin>>n)
{
mem(head,-);
cnt=;
for(int i=;i<=n;i++)
{
cin>>u>>w;
add_edge(i,u,w);
add_edge(u,i,w);
}
mem(dis,);
mem(vis,false);
dfs();
mem(vis,false);
DFS();
for(int i=;i<=n;i++)cout<<max(dis[i][],dis[i][])<<endl;
}
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 6e3 + ;
int dp[N][], a[N];
vector<int> g[N];
int fa[N];
int dfs(int u, int f) {
if(~dp[u][f]) return dp[u][f];
dp[u][f] = ;
if(f) dp[u][f] = a[u];
for (int v : g[u]) {
if(f) dp[u][f] += dfs(v, );
else dp[u][f] += max(dfs(v, ), dfs(v, ));
}
return dp[u][f];
}
int main() {
int n, u, v, rt;
while(~scanf("%d", &n)) {
for (int i = ; i <= n; ++i) scanf("%d", &a[i]), g[i].clear();
for (int i = ; i <= n; ++i) scanf("%d %d", &u, &v), g[v].pb(u), fa[u] = v;
for (int i = ; i <= n; ++i) if(!fa[i]) rt = i;
mem(dp, -);
printf("%d\n", max(dfs(rt, ), dfs(rt, )));
}
return ;
}
思路：树上分组背包
dp[i][j]：表示以i为根节点选取j个的最大值
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = ;
LL dp[N][N];
int w[N];
vector<int> g[N];
int n, m, a, b;
void dfs(int u) {
for (int v : g[u]) {
dfs(v);
}
for (int v : g[u]) {
for (int i = m; i >= ; --i) {
for (int j = i; j >= ; --j) {
dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j]);
}
}
}
if(u) {
for (int j = m; j >= ; --j) {
dp[u][j] = dp[u][j-] + w[u];
}
}
}
int main() {
while(~scanf("%d %d", &n, &m) && (n || m)) {
for (int i = ; i <= n; ++i) g[i].clear();
for (int i = ; i <= n; ++i) {
scanf("%d %d", &a, &b);
g[a].pb(i);
w[i] = b;
}
for (int i = ; i <= n; ++i) for (int j = ; j <= m; ++j) dp[i][j] = ;
dfs();
printf("%lld\n", dp[][m]);
}
return ;
}
思路：点分治
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 1e4 + ;
const int INF = 0x3f3f3f3f;
int son[N], n, k, u, v, w, ans = ;
vector<pii> g[N];
vector<int> deep;
bool vis[N];
void get_sz(int u, int o) {
son[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(!vis[v] && v != o) {
get_sz(v, u);
son[u] += son[v];
}
}
}
pii get_center(int u, int o, int tot) {
pii res = mp(INF, -);
int m = , tmp = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(!vis[v] && v != o) {
res = min(res, get_center(v, u, tot));
m = max(m, son[v]);
tmp += son[v];
}
}
m = max(m, tot-tmp);
res = min(res, mp(m, u));
return res;
}
void get_deep(int u, int o, int d) {
deep.pb(d);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(!vis[v] && v != o) {
get_deep(v, u, d + w);
}
}
}
int cal() {
int res = ;
sort(deep.begin(), deep.end());
for (int l = , r = deep.size()-; l < r; ) {
if(deep[l] + deep[r] <= k) res += r - l++;
else r--;
}
deep.clear();
return res;
}
void solve(int u) {
get_sz(u, u);
pii p = get_center(u, u, son[u]);
int c = p.se;
vis[c] = true;
get_deep(c, c, );
ans += cal();
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
if(!vis[v]) solve(v);
}
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
int w = g[c][i].se;
if(!vis[v]) {
get_deep(v, v, w);
ans -= cal();
}
}
vis[c] = false;
}
int main() {
while(~scanf("%d %d", &n, &k) && (n || k)) {
for (int i = ; i <= n; ++i) g[i].clear(), son[i] = ;
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w});
ans = ;
solve();
printf("%d\n", ans);
}
return ;
}
思路：
dp[i][0]:以i为根的的子树中需要反转多少条边
dp[i][1]:以i为根需要反转多少条边
其中 dp[1][1] = dp[1][0]
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 2e5 + ;
const int INF = 0x3f3f3f3f;
vector<pii> g[N];
int dp[N][];
int n, u, v;
void dfs(int u, int o) {
dp[u][] = ;
for (pii p : g[u]) {
int v = p.fi;
int w = p.se;
if(v == o) continue;
dfs(v, u);
dp[u][] += dp[v][] + w;
}
}
void DFS(int u, int o) {
if(u == ) dp[u][] = dp[u][];
for (pii p : g[u]) {
int v = p.fi;
int w = p.se;
if(v == o) continue;
if(w) dp[v][] = dp[u][] - ;
else dp[v][] = dp[u][] + ;
DFS(v, u);
}
}
int main() {
scanf("%d", &n);
for (int i = ; i <= n; ++i) g[i].clear();
for (int i = ; i < n; ++i) {
scanf("%d %d", &u, &v);
g[u].pb({v, });
g[v].pb({u, });
}
dfs(, );
DFS(, );
int mn = INF;
for (int i = ; i <= n; ++i) mn = min(mn, dp[i][]);
printf("%d\n", mn);
for (int i = ; i <= n; ++i) if(dp[i][] == mn) printf("%d ", i);
printf("\n");
return ;
}
思路：树上分组背包，注意每个节点背包容量不能跑满，跑子树中叶子节点的个数
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 3e3 + ;
const int INF = 0x3f3f3f3f;
int dp[N][N], cnt[N], n, m, k, a, c;
vector<pii> g[N];
int dfs(int u) {
cnt[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
cnt[u] += dfs(v);
}
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
for (int i = cnt[u]; i >= ; --i) {
int up = min(i, cnt[v]);
for (int j = up; j >= ; --j) {
dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j] - w);
}
}
}
if(!cnt[u]) cnt[u] = ;
return cnt[u];
}
int main() {
scanf("%d %d", &n, &m);
for (int i = ; i <= n-m; ++i) {
scanf("%d", &k);
for (int j = ; j <= k; ++j) {
scanf("%d %d", &a, &c);
g[i].pb(mp(a, c));
}
}
for (int i = ; i <= n; ++i) for (int j = ; j <= m; ++j) dp[i][j] = -INF;
for (int i = n-m+; i <= n; ++i) scanf("%d", &dp[i][]);
dfs();
for (int i = m; i >= ; --i) if(dp[][i] >= ) return *printf("%d\n", i);
return ;
}
思路：还是树上分组背包
dp[i][j]表示以i为根节点的子树中保留j个节点（剩下的也和i相连）的最小切边个数
把每条边的权值看成-1，把每个点的权值看成它所连的边的个数（这样就可以最后加上点的权值来使得放进背包里的抵消掉，没放进背包里的就是要切的边的个数）
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = ;
const int INF = 0x3f3f3f3f;
vector<int> g[N];
int dp[N][N], fa[N], n, p, u, v;
int dfs(int u) {
int tot = g[u].size(), son = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
son += dfs(v);
}
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
for (int i = son; i >= ; --i) {
for (int j = i; j >= ; --j) {
dp[u][i] = min(dp[u][i-j] + dp[v][j] - , dp[u][i]);
}
}
}
if(!tot) dp[u][] = ;
else {
for (int i = son; i >= ; --i) dp[u][i] = dp[u][i-] + tot;
}
return son;
}
int main() {
scanf("%d %d", &n, &p);
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), fa[v] = u;
int rt;
for (int i = ; i <= n; ++i) if(!fa[i]) rt = i;
for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j) dp[i][j] = INF;
dfs(rt);
int ans = INF;
for (int i = ; i <= n; ++i) {
if(i == rt) ans = min(ans, dp[i][p]);
else ans = min(ans, dp[i][p]+);
}
printf("%d\n", ans);
return ;
}
思路：还是树上分组背包
有个坑点，具体见代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = ;
LL dp[N][N];
int a[N], b[N], n, m, u, v;
vector<int> g[N];
void dfs(int u, int o) {
int cnt = (a[u]+)/;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) {
dfs(v, u);
for (int i = m; i >= ; --i) {
for (int j = i; j >= ; --j) {
dp[u][i] = max(dp[u][i-j]+dp[v][j], dp[u][i]);
}
}
}
}
for (int i = m; i >= cnt; --i) dp[u][i] = dp[u][i-cnt] + b[u];
for (int i = ; i < cnt; ++i) dp[u][i] = ;//!!!!坑点
dp[u][] = ;
}
int main() {
while(~scanf("%d %d", &n, &m)) {
if(n == - && m == -) break;
for (int i = ; i <= n; ++i) g[i].clear();
for (int i = ; i <= n; ++i) scanf("%d %d", &a[i], &b[i]);
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
for (int i = ; i <= n; ++i) for (int j = ; j <= m; ++j) dp[i][j] = ;
dfs(, );
printf("%lld\n", dp[][m]);
}
return ;
}
/*
5 1
21 1
1 1
1 5
1 1
1 2
1 2
1 3
2 4
2 5
*/
思路：枚举不往同一个方向走的左边界，算出右边界，然后一起往左或往右，口婴
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 1e5 + ;
int n, p, m, t;
int v[N];
LL sum[N];
int main() {
while(~scanf("%d %d", &n, &p)) {
for (int i = ; i <= n; ++i) scanf("%d", &v[i]);
scanf("%d %d", &m, &t);
for (int i = ; i <= n; ++i) sum[i] = sum[i-] + v[i];
LL ans = ;
for (int l = max(, p-t); l <= p; ++l) {
int r = min(n, min(l+m, p+t));
LL tmp = sum[r] - sum[l-];
int res = t - max(p-l, r-p);
int ll = max(, l-res);
int rr = min(n, r+res);
tmp += max(sum[rr] - sum[r], sum[l-] - sum[ll-]);
//cout << tmp << endl;
ans = max(tmp, ans);
}
printf("%lld\n", ans);
}
return ;
}
/*
7 4
11 10 2 10 2 20 2
2 3
*/
思路：
二分 + 树形dp
dp[i]表示切断i所在子树所有叶子的最小花费
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 1e3 + ;
const int INF = 0x3f3f3f3f;
vector<pii> g[N];
LL dp[N];
int n, m, u, v, w;
void dfs(int u, int o, int x) {
for (pii p : g[u]) {
int v = p.fi;
int w = p.se;
if(v != o) {
dfs(v, u, x);
if(w <= x) dp[u] += min((LL)w, dp[v]);
else dp[u] += dp[v];
}
}
if(!dp[u]) dp[u] = INF;
}
bool ck(int mid) {
for (int i = ; i <= n; ++i) dp[i] = ;
dfs(, , mid);
return dp[] <= m;
}
int main() {
while(~scanf("%d %d", &n, &m) && (n || m)) {
for (int i = ; i <= n; ++i) g[i].clear();
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w});
int l = , r = , mid = l+r >> ;
while(l < r) {
if(ck(mid)) r = mid;
else l = mid + ;
mid = l+r >> ;
}
if(mid <= ) printf("%d\n", mid);
else printf("-1\n");
}
return ;
}
思路：
求树的重心
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 5e4 + ;
const int INF = 0x3f3f3f3f;
struct edge {
int to, nxt;
}edge[N*];
int son[N], dp[N], head[N], n, u, v, center, cnt = ;
void add_edge(int u, int v) {
edge[cnt].to = v;
edge[cnt].nxt = head[u];
head[u] = cnt++;
}
void dfs(int u, int o) {
son[u] = ;
int m = ;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != o) {
dfs(v, u);
son[u] += son[v];
m = max(m, son[v]);
}
}
m = max(m, n-son[u]);
center = min(m, center);
dp[u] = m;
}
int main() {
while(~scanf("%d", &n)) {
for (int i = ; i <= n; ++i) son[i] = , head[i] = -;
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), add_edge(u, v), add_edge(v, u);
center = INF;
dfs(, );
for (int i = ; i <= n; ++i) if(dp[i] == center) printf("%d ", i);
printf("\n");
}
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define ABS(a) (a > 0) ? (a) : -(a)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 1e5 + ;
const LL INF = 0x3f3f3f3f3f3f3f3f;
vector<int> g[N];
int a[N], n, m, u, v;
LL son[N], res, tot;
void dfs(int u, int o) {
son[u] = a[u];
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) {
dfs(v, u);
son[u] += son[v];
res = min(res, ABS(tot-son[v]-son[v]));
}
}
}
int main() {
int cs = ;
while(~scanf("%d %d", &n, &m) && (n || m)) {
res = INF, tot = ;
for (int i = ; i <= n; ++i) g[i].clear();
for (int i = ; i <= n; ++i) scanf("%d", &a[i]), tot += a[i];
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
dfs(, );
printf("Case %d: %lld\n", ++cs, res);
}
return ;
}
思路：先树形dp求出离每个点最远的距离，做了这么多题你肯定会了
这道题主要是一个单调队列维护区间极值，然后再用尺取法跑一跑对于每一个右端点，它的左端点在哪里
然后还有建图用链式前向星，poj好几道都卡了这个
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<deque>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define ABS(a) (a > 0) ? (a) : -(a)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 1e6 + ;
const int INF = 0x3f3f3f3f;
struct edge {
int to, w, nxt;
}edge[N*];
int head[N], cnt;
LL dp[N][], dis[N];
int n, m, u, w;
void add_edge(int u, int v, int w) {
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt++;
}
void dfs(int u, int o) {
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
int w = edge[i].w;
if(v != o) {
dfs(v, u);
dp[u][] = max(dp[u][], dp[v][] + w);
}
}
}
void DFS(int u, int o) {
pii mx = mp(, -), mx1 = mp(, -);
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
int w = edge[i].w;
if(v != o) {
if(dp[v][] + w > mx.fi) {
mx1 = mx;
mx.fi = dp[v][] + w;
mx.se = v;
}
else if(dp[v][] + w >= mx1.fi) {
mx1.fi = dp[v][] + w;
mx1.se = v;
}
}
}
if(dp[u][] > mx.fi) {
mx.fi = dp[u][];
mx.se = -;
}
else if(dp[u][] >= mx1.fi) {
mx1.fi = dp[u][];
mx1.se = -;
}
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
int w = edge[i].w;
if(v != o) {
if(v == mx.se) dp[v][] = mx1.fi + w;
else dp[v][] = mx.fi + w;
DFS(v, u);
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = ; i <= n; ++i) head[i] = -;
cnt = ;
for (int i = ; i <= n; ++i) scanf("%d %d", &u, &w), add_edge(i, u, w), add_edge(u, i, w);
dfs(, );
DFS(, );
for (int i = ; i <= n; ++i) dis[i] = max(dp[i][], dp[i][]);
deque<int> q1, q2;
int l = , ans = ;
for (int r = ; r <= n; ++r) {
while(!q1.empty() && dis[q1.back()] > dis[r]) q1.pop_back();
q1.push_back(r);
while(!q2.empty() && dis[q2.back()] < dis[r]) q2.pop_back();
q2.push_back(r);
while(l <= r) {
while(!q1.empty() && q1.front() < l) q1.pop_front();
while(!q2.empty() && q2.front() < l) q2.pop_front();
if(dis[q2.front()] - dis[q1.front()] > m) ++l;
else break;
}
ans = max(ans, r-l+);
}
printf("%d\n", ans);
return ;
}
思路：
这个转移不好想，因为当前节点不仅可以依赖子孙还可以依赖其他节点
这样的话对于当前节点 u 就暴力枚举每个它可能依赖的点 i
dp[u][i]:表示以u为根节点的子树(且 u 依赖 i )的最小花费
son[u]:表示以u为根节点的子树的最小花费，这样的话，只要上面求出来了，这个就求出来了
dp[u][i] = w[i] + sum(min(dp[v][i] - w[i], son[v])) ，其中 u 和 i 之间的距离小于 d[u] ， v 是 u 的儿子
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<deque>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define ABS(a) (a > 0) ? (a) : -(a)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 1e3 + ;
const int INF = 0x3f3f3f3f;
int dis[N][N], dp[N][N], son[N], w[N], d[N], head[N];
int T, n, u, v, W, cnt;
struct edge {
int to, w, nxt;
}edge[N*];
void add_edge(int u, int v, int w) {
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt++;
}
void get_d(int x, int fa, int t) {
dis[u][x] = t;
for (int i = head[x]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
int w = edge[i].w;
if(v != fa) get_d(v, x, t+w);
}
}
void dfs(int u, int o) {
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != o) {
dfs(v, u);
}
}
son[u] = INF;
for (int j = ; j <= n; ++j) {
dp[u][j] = INF;
if(dis[u][j] > d[u]) continue;
dp[u][j] = w[j];
int tot = ;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != o) {
dp[u][j] += min(dp[v][j]-w[j], son[v]);
}
}
//cout << u << " " << j << " " << dp[u][j] << endl;
son[u] = min(son[u], dp[u][j]);
}
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = ; i <= n; ++i) head[i] = -;
cnt = ;
for (int i = ; i <= n; ++i) scanf("%d", &w[i]);
for (int i = ; i <= n; ++i) scanf("%d", &d[i]);
for (int i = ; i < n; ++i) {
scanf("%d %d %d", &u, &v, &W);
add_edge(u, v, W);
add_edge(v, u, W);
}
for (u = ; u <= n; ++u) get_d(u, u, );
dfs(, );
printf("%d\n", son[]);
}
return ;
}
虚树：
https://blog.csdn.net/weixin_37517391/article/details/82744605
建树模板：
void Insert(int u) {
if(top <= ) {
stk[++top] = u;
return ;
}
int l = lca(stk[top], u);
if(l == stk[top]) {
stk[++top] = u;
return ;
}
while(top > && dfn[stk[top-]] >= dfn[l]) {
G[stk[top-]].pb(stk[top]);
--top;
}
if(dfn[stk[top]] > dfn[l]) {
G[l].pb(stk[top]);
stk[top] = l;
}
stk[++top] = u;
}
while(top > ) G[stk[top-]].pb(stk[top]), --top;
--top;
BZOJ 2286
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<deque>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define ABS(a) (a > 0) ? (a) : -(a)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 2e5 + 5e4 + ;
const int INF = 0x3f3f3f3f;
vector<pii> g[N];
vector<int> G[N];
int anc[N][], mn[N], deep[N], a[N], stk[N], dfn[N];
bool vis[N];
int n, u, v, w, m, k, tot = , top = ;
bool cmp(int a, int b) {
return dfn[a] < dfn[b];
}
void dfs(int u, int o) {
deep[u] = deep[o] + ;
dfn[u] = ++tot;
anc[u][] = o;
for (int j = ; j < ; ++j) anc[u][j] = anc[anc[u][j-]][j-];
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o) {
mn[v] = min(mn[u], w);
dfs(v, u);
}
}
}
int lca(int u, int v) {
if(deep[u] < deep[v]) swap(u, v);
for (int i = ; i >= ; --i) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i];
if(u == v) return u;
for (int i = ; i >= ; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
return anc[u][];
}
void Insert(int u) {
if(top <= ) {
stk[++top] = u;
return ;
}
int l = lca(stk[top], u);
if(dfn[l] == dfn[stk[top]]) {
stk[++top] = u;
return ;
}
while(top > && dfn[stk[top-]] >= dfn[l]) {
G[stk[top-]].pb(stk[top]);
--top;
}
if(dfn[stk[top]] > dfn[l]) {
G[l].pb(stk[top]);
stk[top] = l;
}
stk[++top] = u;
}
LL DFS(int u, int o) {
LL res = ;
for (int i = ; i < G[u].size(); ++i) {
int v = G[u][i];
if(v != o) {
res += min((LL)mn[v], DFS(v, u));
}
}
G[u].clear();
if(vis[u]) res = mn[u];
return res;
}
int main() {
scanf("%d", &n);
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w});
mn[] = INF;
dfs(, );
scanf("%d", &m);
while(m--) {
scanf("%d", &k);
for (int i = ; i <= k; ++i) scanf("%d", &a[i]), vis[a[i]] = true;
sort(a+, a++k, cmp);
Insert();
for (int i = ; i <= k; ++i) Insert(a[i]);
while(top > ) G[stk[top-]].pb(stk[top]), --top;
printf("%lld\n", DFS(, ));
for (int i = ; i <= k; ++i) vis[a[i]] = false;
}
return ;
}
思路：
先建虚树，对于某个点，如果它被染色了，那么切断它和所有子孙中还没有被切断的染色节点的联系
如果它没有被染色，那么如果子孙节点中染色节点超过1才把这个点去掉
代码：
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
vector<int> g[N], G[N];
int anc[N][], dfn[N], a[N], deep[N], stk[N], fa[N], sz[N], n, u, v, q, k, res, tot = , top = ;
bool vis[N], f;
void dfs(int u, int o) {
dfn[u] = ++tot;
deep[u] = deep[o] + ;
anc[u][] = o;
for (int i = ; i < ; ++i) anc[u][i] = anc[anc[u][i-]][i-];
for (int v : g[u]) {
if(v != o) {
fa[v] = u;
dfs(v, u);
}
}
}
int lca(int u, int v) {
if(deep[u] < deep[v]) swap(u, v);
for (int i = ; i >= ; --i) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i];
if(u == v) return u;
for (int i = ; i >= ; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
return anc[u][];
}
bool cmp(int a, int b) {
return dfn[a] < dfn[b];
}
void Insert(int u) {
if(top <= ) {
stk[++top] = u;
return ;
}
int l = lca(stk[top], u);
if(l == stk[top]) {
stk[++top] = u;
return ;
}
while(top > && dfn[stk[top-]] >= dfn[l]) {
G[stk[top-]].pb(stk[top]);
--top;
}
if(dfn[stk[top]] > dfn[l]) {
G[l].pb(stk[top]);
stk[top] = l;
}
stk[++top] = u;
}
int DFS(int u) {
int res = ;
sz[u] = ;
for (int v : G[u]) {
res += DFS(v);
sz[u] += sz[v];
}
if(vis[u]) res += sz[u], sz[u] = ;
else if(sz[u] > ) res++, sz[u] = ;
return res;
}
void clr(int u) {
for (int v : G[u]) {
clr(v);
}
sz[u] = ;
G[u].clear();
}
int main() {
scanf("%d", &n);
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
dfs(, );
scanf("%d", &q);
while(q--) {
scanf("%d", &k);
for (int i = ; i <= k; ++i) scanf("%d", &a[i]), vis[a[i]] = true;
f = false;
for (int i = ; i <= k; ++i) {
if(vis[fa[a[i]]]) {
printf("-1\n");
f = true;
break;
}
}
if(f) {
for (int i = ; i <= k; ++i) vis[a[i]] = false;
continue;
}
sort(a+, a++k, cmp);
Insert();
for (int i = ; i <= k; ++i) if(a[i] != ) Insert(a[i]);
while(top > ) G[stk[top-]].pb(stk[top]), --top;
--top;
printf("%d\n", DFS());
clr();
for (int i = ; i <= k; ++i) vis[a[i]] = false;
}
return ;
}
思路：这道题只用到了lca, 对于同一种颜色求出它虚树的直径，考虑nlog(n)求解，
每次添加一个节点，对于这种颜色来说直径必定在原来直径的两个点和当前点两两组合其中一个。
求两个颜色的最长路也同理，在两个颜色虚树直径的四个端点中两两组合其中一个。
代码：
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
vector<int> g[N];
map<string, int> mp;
string s, a, b;
pair<int,pii> diameter[N];
int color[N], anc[N][], deep[N], n, q, u, v, tot;
void dfs(int u, int o) {
anc[u][] = o;
deep[u] = deep[o] + ;
for (int i = ; i < ; ++i) anc[u][i] = anc[anc[u][i-]][i-];
for (int v : g[u]) {
if(v != o) {
dfs(v, u);
}
}
}
inline int lca(int u, int v) {
if(deep[u] < deep[v]) swap(u, v);
for (int i = ; i >= ; --i) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i];
if(u == v) return u;
for (int i = ; i >= ; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
return anc[u][];
}
inline int len(int u, int v) {
return deep[u] + deep[v] - *deep[lca(u, v)];
}
int main() {
fio;
while(cin >> n >> q) {
tot = ;
mp.clear();
for (int i = ; i <= n; ++i) g[i].clear(), diameter[i] = {-, {-, -}}; for (int i = ; i <= n; ++i) {
cin >> s;
if(mp.find(s) == mp.end()) mp[s] = ++tot, color[i] = tot;
else color[i] = mp[s];
}
for (int i = ; i < n; ++i) cin >> u >> v, g[u].pb(v), g[v].pb(u);
deep[] = ;
dfs(, );
for (int i = ; i <= n; ++i) {
int c = color[i];
if(diameter[c].fi == -) diameter[c] = {, {i, i}};
else {
int a = diameter[c].se.fi, b = diameter[c].se.se;
diameter[c] = max(diameter[c], {len(a, i), {a, i}});
diameter[c] = max(diameter[c], {len(b, i), {b, i}});
}
}
while(q--) {
cin >> a >> b;
if(mp.find(a) == mp.end() || mp.find(b) == mp.end()) cout << - << "\n";
else {
int u = mp[a], v = mp[b], res = ;
int x = diameter[u].se.fi, xx = diameter[u].se.se;
int y = diameter[v].se.fi, yy = diameter[v].se.se;
//cout << x << " " << xx << " " << y << " " << yy << endl;
res = max(res, len(x, y));
res = max(res, len(x, yy));
res = max(res, len(xx, y));
res = max(res, len(xx, yy));
cout << res+ << "\n";
}
}
}
return ;
}
https://www.luogu.org/problemnew/show/P3233
坑，会虚不会树
树分治：
点分治主要步骤：
1.得到树的大小
2.计算当前树的重心
3.从重心出发计算链长
4.计算通过重心的链对答案的贡献
5.对于每个重心的儿子，删去两条链都经过儿子对答案的贡献（有些题目不能这样算，考虑边算子树贡献边加子树信息）
6.按重心分治，递归它的每个儿子
Codeforces E - Digit Tree
思路：A = -B*inv(10^B.length) （%M）
代码：
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
const int INF = 0x3f3f3f3f;
int n, MOD, u, v, w;
vector<pii> g[N];
map<int, int> mp1, mp2;
int inv[N], P[N], son[N];
bool vis[N];
pii center;
LL ans = ;
LL q_pow(LL n, LL k) {
if(k < ) return ;
LL res = ;
while(k) {
if(k&) res = (res * n) % MOD;
n = (n * n) % MOD;
k >>= ;
}
return res;
}
int phi(int n) {
int res = n;
for (int i = ; i*i <= n; ++i) {
if(n%i == ) {
res = res/i*(i-);
while(n%i == ) n /= i;
}
}
if(n > ) res = res/n*(n-);
return res;
}
void init() {
P[] = %MOD;
for (int i = ; i < N; ++i) P[i] = P[i-]*10LL%MOD;
inv[N-] = q_pow(P[N-], phi(MOD)-);
for (int i = N-; i >= ; --i) inv[i] = inv[i+]*10LL%MOD;
}
inline void get_sz(int u, int o) {
son[u] = ;
for (pii p : g[u]) {
int v = p.fi;
if(v != o && !vis[v]) {
get_sz(v, u);
son[u] += son[v];
}
}
}
inline void get_center(int u, int o, int tot) {
int mx = ;
for (pii p : g[u]) {
int v = p.fi;
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, son[v]);
}
}
mx = max(mx, tot - son[u]);
center = min(center, {mx, u});
}
inline void get_deep(int u, int o, int a, int b, int d) {
for (pii p : g[u]) {
int v = p.fi;
int w = p.se;
if(v != o && !vis[v]) {
get_deep(v, u, (w*1LL*P[d]+a)%MOD, (b*10LL+w)%MOD, d+);
}
}
mp1[a]++, mp2[((MOD-b)*1LL*inv[d])%MOD]++;
}
inline LL cal() {
LL res = ;
for (auto it : mp1) {
if(mp2.find(it.fi) != mp2.end()) {
res += 1LL*it.se*mp2[it.fi];
}
}
mp1.clear();
mp2.clear();
return res;
}
inline void solve(int u) {
get_sz(u, u);
center = {INF, INF};
get_center(u, u, son[u]);
int c = center.se;
vis[c] = true;
get_deep(c, c, , , );
ans += cal()-;
for (pii p : g[c]) {
int v = p.fi;
int w = p.se;
if(!vis[v]) {
get_deep(v, c, w%MOD, w%MOD, );
ans -= cal();
}
}
for (pii p : g[c]) {
int v = p.fi;
if(!vis[v]) solve(v);
}
vis[c] = false;
}
int main() {
scanf("%d %d", &n, &MOD);
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w});
init();
solve();
printf("%lld\n", ans);
return ;
}
Codeforces E - Palindromes in a Tree
思路：对于每条链如果状压后只有一个1或者没有1就说明可以构成回文串
对于每个分治点，如果要计算某个子树上每个点的答案，先把这课子树先清空
（因为这条链必须经过分治点，肯定来自其他子树），还有儿子的答案它父亲肯定也有
最后计算分治点的答案
代码：
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 2e5 + ;
const int INF = 0x3f3f3f3f;
vector<int> g[N];
int son[N], cnt[<<], n, u, v;
LL ans[N];
char s[N];
bool vis[N];
pii center;
inline void get_sz(int u, int o) {
son[u] = ;
for (int v : g[u]) {
if(v != o && !vis[v]) {
get_sz(v, u);
son[u] += son[v];
}
}
}
inline void get_center(int u, int o, int tot) {
int mx = ;
for (int v : g[u]) {
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, son[v]);
}
}
mx = max(mx, tot - son[u]);
center = min(center, {mx, u});
}
inline void update(int u, int o, int st, int ty) {
cnt[st] += ty;
for (int v : g[u]) {
if(v != o && !vis[v]) {
update(v, u, st^(<<s[v]-'a'), ty);
}
}
}
inline LL cal(int u, int o, int st) {
LL res = ;
for (int v : g[u]) {
if(v != o && !vis[v]) {
res += cal(v, u, st^(<<s[v]-'a'));
}
}
res += cnt[st];
for (int i = ; i < ; ++i) {
res += cnt[st^(<<i)];
}
ans[u] += res;
return res;
}
inline void solve(int u) {
get_sz(u, u);
center = {INF, INF};
get_center(u, u, son[u]); int c = center.se;
vis[c] = true;
int st = <<s[c]-'a';
update(c, c, st, );
LL tmp = ;
for (int v : g[c]) {
if(!vis[v]) {
update(v, c, st^(<<s[v]-'a'), -);
tmp += cal(v, c, <<s[v]-'a');
update(v, c, st^(<<s[v]-'a'), );
}
}
tmp += cnt[];
for (int i = ; i < ; ++i)tmp += cnt[<<i];
ans[c] += tmp/;
update(c, c, st, -);
for (int v : g[c]) {
if(!vis[v]) solve(v);
}
vis[c] = false;
}
int main() {
scanf("%d", &n);
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
scanf("%s", s+);
solve();
for (int i = ; i <= n; ++i) printf("%lld ", ans[i]+);
return ;
}
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e4 + , NN = 1e7 + , M = 1e2 + ;
const int INF = 0x3f3f3f3f;
vector<pii> g[N];
bool vis[N], ans[M];
pii center;
int Q[N], son[N], cnt[NN], n, m, u, w, q;
void get_sz(int u, int o) {
son[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) {
get_sz(v, u);
son[u] += son[v];
}
}
}
void get_center(int u, int o, int tot) {
int mx = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, son[v]);
}
}
mx = max(mx, tot - son[u]);
center = min(center, {mx, u});
}
void update(int u, int o, int len, int ty) {
cnt[len] += ty;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o && !vis[v]) {
update(v, u, len+w, ty);
}
}
}
void cal(int u, int o, int len) {
for (int i = ; i <= m; ++i) {
if(ans[i]) continue;
if(Q[i]-len >= ) if(cnt[Q[i]-len]) ans[i] = true;
}
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o && !vis[v]) {
cal(v, u, len+w);
}
}
}
void solve(int u) {
get_sz(u, u);
center = {INF, INF};
get_center(u, u, son[u]);
int c = center.se;
vis[c] = true;
update(c, c, , );
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
int w = g[c][i].se;
if(!vis[v]) {
update(v, c, w, -);
cal(v, u, w);
update(v, c, w, );
}
}
update(c, c, , -);
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
if(!vis[v]) solve(v);
}
vis[c] = false;
}
int main() {
while(~scanf("%d", &n) && n) {
for (int i = ; i <= n; ++i) g[i].clear();
for (int i = ; i <= n; ++i) {
while(~scanf("%d", &u) && u) {
scanf("%d", &w);
g[i].pb({u, w});
g[u].pb({i, w});
}
}
m = ;
while(~scanf("%d", &q) && q) Q[++m] = q;
mem(ans, false);
solve();
for (int i = ; i <= m; ++i) {
if(ans[i]) printf("AYE\n");
else printf("NAY\n");
}
printf(".\n");
}
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 3e4 + ;
const int INF = 0x3f3f3f3f;
vector<pii> g[N], G[N];
int son[N], n, m, k, u, v, w;
int d[N];
pii D[N], center;
pair<int,LL> res;
bool vs[N], vis[N];
priority_queue<pii, vector<pii>, greater<pii> > q;
void dijkstra(int s) {
mem(d, 0x3f);
d[s] = ;
q.push(mp(, s));
while(!q.empty()) {
pii p = q.top();
q.pop();
int u = p.se;
if(d[u] < p.fi) continue;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push(mp(d[v], v));
}
}
}
}
void dfs(int u) {
vs[u] = true;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(!vs[v]) {
if(d[u] + w == d[v]) {
G[u].pb(mp(v, w));
G[v].pb(mp(u, w));
dfs(v);
}
}
}
}
void get_sz(int u, int o) {
son[u] = ;
for (int i = ; i < G[u].size(); ++i) {
int v = G[u][i].fi;
int w = G[u][i].se;
if(v != o && !vis[v]) {
get_sz(v, u);
son[u] += son[v];
}
}
}
void get_center(int u, int o, int tot) {
int mx = ;
for (int i = ; i < G[u].size(); ++i) {
int v = G[u][i].fi;
int w = G[u][i].se;
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, son[v]);
}
}
mx = max(mx, tot - son[u]);
center = min(center, mp(mx, u));
}
void update(int u, int o, int x, int d, int ty) {
if(ty == ) {
if(x > D[d].fi) {
D[d].fi = x;
D[d].se = ;
}
else if(x == D[d].fi) D[d].se++;
}
else D[d] = mp(, );
for (int i = ; i < G[u].size(); ++i) {
int v = G[u][i].fi;
int w = G[u][i].se;
if(v != o && !vis[v]) update(v, u, x+w, d+, ty);
}
}
void cal(int u, int o, int x, int d) {
if(d <= k-) {
if(D[k--d].fi + x > res.fi && D[k--d].se > ) {
res.fi = D[k--d].fi + x;
res.se = D[k--d].se;
}
else if(D[k--d].fi + x == res.fi && D[k--d].se > ) {
res.se += D[k--d].se;
}
}
else return;
for (int i = ; i < G[u].size(); ++i) {
int v = G[u][i].fi;
int w = G[u][i].se;
if(v != o && !vis[v]) cal(v, u, x+w, d+);
}
}
void solve(int u) {
get_sz(u, u);
center = {INF, INF};
get_center(u, u, son[u]);
int c = center.se;
vis[c] = true; D[] = mp(, ); for (int i = ; i < G[c].size(); ++i) {
int v = G[c][i].fi;
int w = G[c][i].se;
if(!vis[v]) {
cal(v, c, w, );
update(v, c, w, , );
}
}
update(c, c, , , -);
for (int i = ; i < G[c].size(); ++i) {
int v = G[c][i].fi;
if(!vis[v]) solve(v);
}
vis[c] = false;
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for (int i = ; i <= m; ++i) {
scanf("%d %d %d", &u, &v, &w);
g[u].pb(mp(v, w));
g[v].pb(mp(u, w));
}
for (int i = ; i <= n; ++i) sort(g[i].begin(), g[i].end());
dijkstra();
dfs(); res = mp(, );
for (int i = ; i <= n+; ++i) D[i] = mp(, );
solve();
printf("%d %lld\n", res.fi, res.se);
return ;
}
BZOJ 2152: 聪聪可可
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 2e4 + ;
const int INF = 0x3f3f3f3f;
vector<pii> g[N];
int son[N], cnt[], n, u, v, w;
bool vis[N];
pii center;
LL tot = ;
void get_sz(int u, int o) {
son[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) {
get_sz(v, u);
son[u] += son[v];
}
}
}
void get_center(int u, int o, int tot) {
int mx = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, son[v]);
}
}
mx = max(mx, tot-son[u]);
center = min(center, mp(mx, u));
}
void cal(int u, int o, int x) {
tot += cnt[(-x)%];
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o && !vis[v]) {
cal(v, u, (x+w)%);
}
}
}
void update(int u, int o, int x) {
cnt[x]++;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o && !vis[v]) {
update(v, u, (x+w)%);
}
}
}
void solve(int u) {
get_sz(u, u);
center = mp(INF, INF);
get_center(u, u, son[u]);
int c = center.se;
vis[c] = true;
cnt[]++;
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
int w = g[c][i].se;
if(!vis[v]) {
cal(v, c, w%);
update(v, c, w%);
}
}
cnt[] = cnt[] = cnt[] = ;
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
if(!vis[v]) {
solve(v);
}
}
vis[c] = false;
}
int main() {
scanf("%d", &n);
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w});
solve();
tot = (tot<<) + n;
LL sum = n*1LL*n;
LL d = __gcd(tot, sum);
printf("%lld/%lld\n", tot/d, sum/d);
return ;
}
思路：点分治，树状数组维护前缀最小值
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 2e4 + ;
const int INF = 0x3f3f3f3f;
vector<pair<int, pii>> g[N];
int son[N], T, n, u, v, c, b, C, ans;
pii center;
bool vis[N];
int bit[N], sz;
vector<int> vc;
void add(int x, int a) {
while(x <= sz) bit[x] = max(bit[x], a), x += x&-x;
}
int query(int x) {
int res = ;
while(x) res = max(res, bit[x]), x -= x&-x;
return res;
}
void get_sz(int u, int o) {
son[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && ! vis[v]) {
get_sz(v, u);
son[u] += son[v];
}
}
}
void get_center(int u, int o, int tot) {
int mx = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, son[v]);
}
}
mx = max(mx, tot - son[u]);
center = min(center, mp(mx, u));
}
void get_d(int u, int o, int d) {
vc.pb(d);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se.fi;
if(v != o && !vis[v]) {
get_d(v, u, d+w);
}
}
}
void update(int u, int o, int x, int y) {
add(lower_bound(vc.begin(), vc.end(), x)-vc.begin()+, y);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int xx = g[u][i].se.fi;
int yy = g[u][i].se.se;
if(v != o && !vis[v]) {
update(v, u, x+xx, y+yy);
}
}
}
void cal(int u, int o, int x, int y) {
if(x > C) return ;
int id = upper_bound(vc.begin(), vc.end(), C-x) - vc.begin();
ans = max(ans, query(id)+y);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int xx = g[u][i].se.fi;
int yy = g[u][i].se.se;
if(v != o && !vis[v]) {
cal(v, u, x+xx, y+yy);
}
}
}
void solve(int u) {
get_sz(u, u);
center = mp(INF, INF);
get_center(u, u, son[u]);
int c = center.se;
vis[c] = true;
get_d(c, c, );
sz = vc.size();
sort(vc.begin(), vc.end());
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
int w = g[c][i].se.fi;
int vv = g[c][i].se.se;
if(!vis[v]) {
cal(v, c, w, vv);
update(v, c, w, vv);
}
}
vc.clear();
for (int i = ; i <= sz; ++i) bit[i] = ;
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
if(!vis[v]) solve(v);
}
vis[c] = false;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = ; i < n; ++i) scanf("%d %d %d %d", &u, &v, &c, &b), g[u].pb({v, {c, b}}), g[v].pb({u, {c, b}});
scanf("%d", &C);
ans = ;
solve();
printf("%d\n", ans);
for (int i = ; i <= n; ++i) g[i].clear();
}
return ;
}
思路：还是套个树状数组，但有点坑
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 2e5 + ;
const int INF = 0x3f3f3f3f;
vector<pii> g[N];
int n, m, k, u, v, w, up;
LL ans = ;
int bit[N], son[N], crow[N];
pii center;
bool vis[N];
void add(int x, int a) {
while(x <= up) bit[x] = max(bit[x], a), x += x&-x;
}
int query(int x) {
int res = -INF;
if(x > up) x = up;
while(x) res = max(res, bit[x]), x -= x&-x;
return res;
}
void get_sz(int u, int o) {
son[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) {
get_sz(v, u);
son[u] += son[v];
}
}
}
void get_center(int u, int o, int tot) {
int mx = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, son[v]);
}
}
mx = max(mx, tot-son[u]);
center = min(center, {mx, u});
}
void get_d(int u, int o, int x) {
up = max(up, x);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != o && !vis[v]) get_d(v, u, x+crow[v]);
}
}
void update(int u, int o, int x, int y) {
add(x, y);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o && !vis[v]) {
update(v, u, x+crow[v], y+w);
}
}
}
void cal(int u, int o, int x, int y) {
if(x > k) return ;
int t = query(k-x+);
if(t >= ) ans = max(ans, 1LL*y+t);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o && !vis[v]) {
cal(v, u, x+crow[v], y+w);
}
}
}
void solve(int u) {
get_sz(u, u);
center = {INF, INF};
get_center(u, u, son[u]);
int c = center.se;
vis[c] = true;
up = ;
get_d(c, c, crow[c]+);
for (int i = ; i <= up; ++i) bit[i] = -INF;
if(crow[c]) add(, );
else add(, );
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
int w = g[c][i].se;
if(!vis[v]) {
cal(v, c, crow[v], w);
update(v, c, crow[c]+crow[v]+, w);
}
}
for (int i = ; i < g[c].size(); ++i) {
int v = g[c][i].fi;
if(!vis[v]) solve(v);
}
vis[c] = false;
}
int main() {
scanf("%d %d %d", &n, &k, &m);
for (int i = ; i <= m; ++i) scanf("%d", &u), crow[u] = ;
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w});
solve();
printf("%lld\n", max(ans, 0LL));
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
struct edge {
int to, nxt;
}edge[N*];
int n, u, v, c[N], sz[N], num[N], head[N], tot;
LL ans[N], szsum[N], sum, cnt, res;
bool vis[N];
pii center;
void get_center(int u, int o, int tot) {
int mx = ;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != o && !vis[v]) {
get_center(v, u, tot);
mx = max(mx, sz[v]);
}
}
mx = max(mx, tot-sz[u]);
center = min(center, {mx, u}); }
void update(int u, int o, int f, bool x) {
num[c[u]]++;
if(x) sz[u] = ;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != o && !vis[v]) {
update(v, u, f, x);
if(x) sz[u] += sz[v];
}
}
if(num[c[u]] == ) {
szsum[c[u]] += f*sz[u];
sum += f*sz[u];
} num[c[u]]--;
}
void get_ans(int u, int o) {
num[c[u]]++;
if(num[c[u]] == ) {
++cnt;
sum -= szsum[c[u]];
}
ans[u] += sum + cnt*res;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != o && !vis[v]) {
get_ans(v, u);
}
}
if(num[c[u]] == ) {
--cnt;
sum += szsum[c[u]];
}
num[c[u]]--;
}
void solve(int u, int tot) {
center = {INT_MAX, INT_MAX};
get_center(u, u, tot); int ct = center.se;
vis[ct] = true;
sum = cnt = ;
update(ct, ct, , );
ans[ct] += sum;
for (int i = head[ct]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(!vis[v]) {
num[c[ct]]++;
update(v, v, -, );
num[c[ct]]--; res = sz[ct]-sz[v];
sum -= sz[ct];
szsum[c[ct]] -= sz[ct];
num[c[ct]]++;
++cnt;
get_ans(v, v);
--cnt;
num[c[ct]]--;
szsum[c[ct]] += sz[ct];
sum += sz[ct]; num[c[ct]]++;
update(v, v, , );
num[c[ct]]--;
}
}
update(ct, ct, -, );
for (int i = head[ct]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(!vis[v]) solve(v, sz[v]);
}
vis[ct] = false;
}
void add_edge(int u, int v) {
edge[tot].to = v;
edge[tot].nxt = head[u];
head[u] = tot++;
}
int main() {
scanf("%d", &n);
for (int i = ; i <= n; ++i) scanf("%d", &c[i]);
tot = ;
for (int i = ; i <= n; ++i) head[i] = -;
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), add_edge(u, v), add_edge(v, u);
solve(, n);
for (int i = ; i <= n; ++i) printf("%lld\n", ans[i]);
return ;
}
边分治：
坑
树上差分：
https://www.cnblogs.com/ice-wing/p/7709311.html
BZOJ 4326: NOIP2015 运输计划
思路：二分+边差分（洛谷卡tarjan求lca
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 3e5 + ;
vector<pii> g[N];
int n, m, u, v, w, tot, mx;
int cnt[N], deep[N], len[N], anc[N][];
struct node {
int u, v, a, len;
}a[N];
void dfs(int u, int o) {
anc[u][] = o;
deep[u] = deep[o] + ;
for (int i = ; i < ; ++i) anc[u][i] = anc[anc[u][i-]][i-];
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o) len[v] = len[u] + w, dfs(v, u);
}
}
int lca(int u, int v) {
if(deep[u] < deep[v]) swap(u, v);
for (int i = ; i >= ; --i) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i];
if(u == v) return u;
for (int i = ; i >= ; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
return anc[u][];
}
void DFS(int u, int o, int w) {
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v != o) {
DFS(v, u, w);
cnt[u] += cnt[v];
}
}
if(cnt[u] == tot) mx = max(mx, w);
}
bool ck(int x) {
for (int i = ; i <= n; ++i) cnt[i] = ;
tot = ;
mx = ;
int MX = ;
for (int i = ; i <= m; ++i) {
if(a[i].len > x) {
cnt[a[i].u]++;
cnt[a[i].v]++;
cnt[a[i].a] -= ;
tot++;
}
MX = max(MX, a[i].len);
}
if(tot == ) return true;
DFS(, , );
return MX-mx <= x;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w});
dfs(, );
int l = , r = ;
for (int i = ; i <= m; ++i) {
scanf("%d %d", &a[i].u, &a[i].v);
a[i].a = lca(a[i].u, a[i].v);
a[i].len = len[a[i].u] + len[a[i].v] - *len[a[i].a];
r = max(r, a[i].len);
}
int mid = l+r >> ;
while(l < r) {
if(ck(mid)) r = mid;
else l = mid+;
mid = l+r >> ;
}
printf("%d\n", mid);
return ;
}
思路：点差分
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 5e4 + ;
vector<int> g[N];
int anc[N][], fa[N], deep[N], cnt[N], n, k, u, v, a, ans = ;
void dfs(int u, int o) {
anc[u][] = o;
if(u == ) fa[u] = ;
else fa[u] = o;
deep[u] = deep[o] + ;
for (int i = ; i < ; ++i) anc[u][i] = anc[anc[u][i-]][i-];
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) dfs(v, u);
}
}
int lca(int u, int v) {
if(deep[u] < deep[v]) swap(u, v);
for (int i = ; i >= ; --i) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i];
if(u == v) return u;
for (int i = ; i >= ; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
return anc[u][];
}
void DFS(int u, int o) {
for (int i = ; i < g[u].size(); ++i){
int v = g[u][i];
if(v != o) {
DFS(v, u);
cnt[u] += cnt[v];
}
}
ans = max(ans, cnt[u]);
}
int main() {
scanf("%d %d", &n, &k);
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
dfs(, );
for (int i = ; i <= k; ++i) {
scanf("%d %d", &u, &v);
a = lca(u, v);
cnt[u]++;
cnt[v]++;
cnt[a]--;
cnt[fa[a]]--;
}
DFS(, );
printf("%d\n", ans);
return ;
}
树链剖分：
https://www.cnblogs.com/ivanovcraft/p/9019090.html
模板：
const int N = 1e5 + ;
vector<int> g[N];
int fa[N], dp[N], sz[N], son[N], top[N], dfn[N], to[N], cnt = , n;
void dfs1(int u, int o) {
fa[u] = o;
sz[u] = ;
dp[u] = dp[o] + ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) {
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
to[cnt] = u;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
void add(int u, int v, int x) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) update(dfn[fu], dfn[u], x, , , n), u = fa[fu], fu = top[u];
else update(dfn[fv], dfn[v], x, , , n), v = fa[fv], fv = top[v];
}
if(dfn[u] <= dfn[v]) update(dfn[u], dfn[v], x, , , n);
else update(dfn[v], dfn[u], x, , , n);
}
int sum(int u, int v) {
int ans = , fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) ans += query(dfn[fu], dfn[u], , , n), u = fa[fu], fu = top[u];
else ans += query(dfn[fv], dfn[v], , , n), v = fa[fv], fv = top[v];
}
if(dfn[u] <= dfn[v]) ans += query(dfn[u], dfn[v], , , n);
else ans += query(dfn[v], dfn[u], , , n);
return ans;
}
int lca(int u, int v) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) u = fa[fu], fu = top[u];
else v = fa[fv], fv = top[v];
}
if(dp[u] <= dp[v]) return u;
else return v;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
vector<int> g[N];
int fa[N], dp[N], sz[N], son[N], top[N], dfn[N], to[N], cnt = , n, m, r, MOD;
int a[N], op, x, y, z, u, v, tree[N<<], lazy[N<<];
void push_up(int rt) {
tree[rt] = (tree[rt<<] + tree[rt<<|]) % MOD;
}
void push_down(int rt, int len) {
lazy[rt<<] = (lazy[rt<<] + lazy[rt]) % MOD;
lazy[rt<<|] = (lazy[rt<<|] + lazy[rt]) % MOD;
tree[rt<<] = (tree[rt<<] + (len-(len>>))*1LL*lazy[rt]) % MOD;
tree[rt<<|] = (tree[rt<<|] + (len>>)*1LL*lazy[rt]) % MOD;
lazy[rt] = ;
}
void build(int rt, int l, int r) {
if(l == r) {
tree[rt] = a[to[l]];
return ;
}
int m = l+r >> ;
build(ls);
build(rs);
push_up(rt);
}
void update(int L, int R, int x, int rt, int l, int r) {
if(L <= l && r <= R) {
lazy[rt] = (lazy[rt] + x) % MOD;
tree[rt] = (tree[rt] + (r-l+)*1LL*x) % MOD;
return ;
}
if(lazy[rt]) push_down(rt, r-l+);
int m = l+r >> ;
if(L <= m) update(L, R, x, ls);
if(R > m) update(L, R, x, rs);
push_up(rt);
}
int query(int L, int R, int rt, int l, int r) {
if(L <= l && r <= R) return tree[rt];
int ans = , m = l+r >> ;
if(lazy[rt]) push_down(rt, r-l+);
if(L <= m) ans = (ans + query(L, R, ls)) % MOD;
if(R > m) ans = (ans + query(L, R, rs)) % MOD;
push_up(rt);
return ans;
}
void dfs1(int u, int o) {
fa[u] = o;
sz[u] = ;
dp[u] = dp[o] + ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) {
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
to[cnt] = u;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
void add(int u, int v, int x) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) update(dfn[fu], dfn[u], x, , , n), u = fa[fu], fu = top[u];
else update(dfn[fv], dfn[v], x, , , n), v = fa[fv], fv = top[v];
}
if(dfn[u] <= dfn[v]) update(dfn[u], dfn[v], x, , , n);
else update(dfn[v], dfn[u], x, , , n);
}
int sum(int u, int v) {
int ans = , fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) ans = (ans + query(dfn[fu], dfn[u], , , n)) % MOD, u = fa[fu], fu = top[u];
else ans = (ans + query(dfn[fv], dfn[v], , , n)) % MOD, v = fa[fv], fv = top[v];
}
if(dfn[u] <= dfn[v]) ans = (ans + query(dfn[u], dfn[v], , , n)) % MOD;
else ans = (ans + query(dfn[v], dfn[u], , , n)) % MOD;
return ans;
}
int lca(int u, int v) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) u = fa[fu], fu = top[u];
else v = fa[fv], fv = top[v];
}
if(dp[u] <= dp[v]) return u;
else v;
}
int main() {
scanf("%d %d %d %d", &n, &m, &r, &MOD);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]);
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
dfs1(r, r);
dfs2(r, r);
build(, , n);
for (int i = ; i <= m; ++i) {
scanf("%d", &op);
if(op == ) {
scanf("%d %d %d", &x, &y, &z);
add(x, y, z);
}
else if(op == ) {
scanf("%d %d", &x, &y);
printf("%lld\n", sum(x, y));
}
else if(op == ) {
scanf("%d %d", &x, &z);
update(dfn[x], dfn[x]+sz[x]-, z, , , n);
}
else {
scanf("%d", &x);
printf("%d\n", query(dfn[x], dfn[x]+sz[x]-, , , n));
}
}
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
vector<int> g[N];
int sz[N], fa[N], dp[N], son[N], top[N], dfn[N], to[N], cnt = ;
int n, q, u, x;
int tree[N<<], lazy[N<<];
char s[];
void push_up(int rt) {
tree[rt] = tree[rt<<] + tree[rt<<|];
}
void push_down(int rt, int len) {
lazy[rt<<] = lazy[rt];
lazy[rt<<|] = lazy[rt];
tree[rt<<] = lazy[rt]*(len-(len>>));
tree[rt<<|] = lazy[rt]*(len>>);
lazy[rt] = -;
}
void build(int rt, int l, int r) {
lazy[rt] = -;
if(l == r) return ;
int m = l+r >> ;
build(ls);
build(rs);
}
void update(int L, int R, int x, int rt, int l, int r) {
if(L <= l && r <= R) {
tree[rt] = x*(r-l+);
lazy[rt] = x;
return ;
}
if(~lazy[rt]) push_down(rt, r-l+);
int m = l+r >> ;
if(L <= m) update(L, R, x, ls);
if(R > m) update(L, R, x, rs);
push_up(rt);
}
int query(int L, int R, int rt, int l, int r) {
if(L <= l && r <= R) return tree[rt];
if(~lazy[rt]) push_down(rt, r-l+);
int ans = , m = l+r >> ;
if(L <= m) ans += query(L, R, ls);
if(R > m) ans += query(L, R, rs);
push_up(rt);
return ans;
}
void dfs1(int u, int o) {
fa[u] = o;
dp[u] = dp[o] + ;
sz[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) {
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
dfn[u] = ++cnt;
to[cnt] = u;
top[u] = t;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != son[u] && v != fa[u]) dfs2(v, v);
}
}
void add(int u, int v, int x) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] < dp[fv]) swap(u, v), swap(fu, fv);
update(dfn[fu], dfn[u], x, , , n);
u = fa[fu];
fu = top[u];
}
if(dfn[u] <= dfn[v]) update(dfn[u], dfn[v], x, , , n);
else update(dfn[v], dfn[u], x, , , n);
}
int sum(int u, int v) {
int ans = , fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] < dp[fv]) swap(u, v), swap(fu, fv);
ans += query(dfn[fu], dfn[u], , , n);
u = fa[fu];
fu = top[u];
}
if(dfn[u] <= dfn[v]) ans += query(dfn[u], dfn[v], , , n);
else ans += query(dfn[v], dfn[u], , , n);
return ans;
}
int main() {
scanf("%d", &n);
for (int i = ; i <= n; ++i) scanf("%d", &u), u++, g[u].pb(i);
dfs1(, );
dfs2(, );
build(, , n);
scanf("%d", &q);
for (int i = ; i <= q; ++i){
scanf("%s", s);
scanf("%d", &u);
++u;
if(s[] == 'i') {
printf("%d\n", dp[u] - sum(, u));
add(, u, );
}
else {
printf("%d\n", query(dfn[u], dfn[u]+sz[u]-, , , n));
update(dfn[u], dfn[u]+sz[u]-, , , , n);
}
}
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 3e5 + ;
vector<int> g[N];
int sz[N], fa[N], dp[N], son[N], top[N], dfn[N], to[N], cnt = ;
int n, m, u, v, x;
int a[N];
char s[];
struct node {
int l, r, cnt, lazy;
}tree[N<<];
void push_up(int rt) {
tree[rt].cnt = tree[rt<<].cnt + tree[rt<<|].cnt;
if(tree[rt<<].r == tree[rt<<|].l) tree[rt].cnt--;
tree[rt].l = tree[rt<<].l;
tree[rt].r = tree[rt<<|].r;
}
void push_down(int rt) {
tree[rt<<] = tree[rt<<|] = {tree[rt].lazy, tree[rt].lazy, , tree[rt].lazy};
tree[rt].lazy = ;
}
node Merge(node a, node b) {
node ans;
if(!a.cnt) return b;
else if(!b.cnt) return a;
ans.l = a.l;
ans.r = b.r;
ans.cnt = a.cnt + b.cnt;
if(a.r == b.l) ans.cnt--;
return ans;
}
void build(int rt, int l, int r) {
tree[rt].lazy = ;
if(l == r) {
tree[rt].l = tree[rt].r = a[to[l]];
tree[rt].cnt = ;
return ;
}
int m = l+r >> ;
build(ls);
build(rs);
push_up(rt);
}
void update(int L, int R, int x, int rt, int l, int r) {
if(L <= l && r <= R) {
tree[rt].lazy = tree[rt].l = tree[rt].r = x;
tree[rt].cnt = ;
return ;
}
if(tree[rt].lazy) push_down(rt);
int m = l+r >> ;
if(L <= m) update(L, R, x, ls);
if(R > m) update(L, R, x, rs);
push_up(rt);
}
node query(int L, int R, int rt, int l, int r) {
if(L <= l && r <= R) return tree[rt];
if(tree[rt].lazy) push_down(rt);
int m = l+r >> ;
node ans = {, , , };
if(L <= m) ans = query(L, R, ls);
if(R > m) ans = Merge(ans, query(L, R, rs));
push_up(rt);
return ans;
}
void add(int u, int v, int x) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] < dp[fv]) swap(u, v), swap(fu, fv);
update(dfn[fu], dfn[u], x, , , n);
u = fa[fu];
fu = top[u];
}
if(dfn[u] <= dfn[v]) update(dfn[u], dfn[v], x, , , n);
else update(dfn[v], dfn[u], x, , , n);
}
int sum(int u, int v) {
node l = {, , , }, r = {, , , };
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) {
l = Merge(query(dfn[fu], dfn[u], , , n), l);
u = fa[fu];
fu = top[u];
}
else {
r = Merge(query(dfn[fv], dfn[v], , , n), r);
v = fa[fv];
fv = top[v];
}
}
if(dfn[u] <= dfn[v]) r = Merge(query(dfn[u], dfn[v], , , n), r);
else l = Merge(query(dfn[v], dfn[u], , , n), l);
swap(l.l, l.r);
l = Merge(l, r);
return l.cnt;
}
void dfs1(int u, int o) {
dp[u] = dp[o] + ;
fa[u] = o;
sz[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) {
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
to[cnt] = u;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = ; i <= n; ++i) scanf("%d", &a[i]);
for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
dfs1(, );
dfs2(, );
build(, , n);
for (int i = ; i <= m; ++i) {
scanf("%s", s);
if(s[] == 'Q') {
scanf("%d %d", &u, &v);
printf("%d\n", sum(u, v));
}
else {
scanf("%d %d %d", &u, &v, &x);
add(u, v, x);
}
}
return ;
}
代码：
#pragma comment(linker,"/STACK:100000000,100000000")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 5e4 + ;
struct edge {
int to, nxt;
}edge[N*];
int head[N], tot = ;
int a[N], n, m, p, u, v, k;
int sz[N], dp[N], fa[N], son[N], dfn[N], top[N], to[N], cnt = ;
int bit[N];
char s[];
inline int read(){
int s=,w=;
char ch=getchar();
while(ch<=''||ch>''){if(ch=='-')w=-;ch=getchar();}
while(ch>=''&&ch<='') s=s*+ch-'',ch=getchar();
return s*w;
}
void add(int u, int v) {
edge[tot].to = v;
edge[tot].nxt = head[u];
head[u] = tot++;
}
void dfs1(int u, int o) {
dp[u] = dp[o] + ;
sz[u] = ;
fa[u] = o;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != o) {
dfs1(v, u);
sz[u] += sz[v];
if(sz[son[u]] < sz[v]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
to[cnt] = u;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
inline void update(int x, int a) {
while(x <= n) bit[x] += a, x += x&-x;
}
inline int query(int x) {
int ans = ;
while(x) ans += bit[x], x -= x&-x;
return ans;
}
void add(int u, int v, int x) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] < dp[fv]) swap(u, v), swap(fu, fv);
update(dfn[fu], x);
update(dfn[u]+, -x);
u = fa[fu];
fu = top[u];
}
if(dfn[u] <= dfn[v]) update(dfn[u], x), update(dfn[v]+, -x);
else update(dfn[v], x), update(dfn[u]+, -x);
}
int main() {
while(~scanf("%d %d %d", &n, &m, &p)) {
for (int i = ; i <= n; ++i) a[i] = read();
for (int i = ; i <= m; ++i) u = read(), v = read(), add(u, v), add(v, u);
cnt = ;
dp[] = ;
dfs1(, );
dfs2(, );
for (int i = ; i <= n; ++i) update(dfn[i], a[i]), update(dfn[i]+, -a[i]);
for (int i = ; i <= p; ++i) {
scanf("%s", s);
if(s[] == 'I') {
u = read();
v = read();
k = read();
add(u, v, k);
}
else if(s[] == 'D') {
u = read();
v = read();
k = read();
add(u, v, -k);
}
else {
u = read();
printf("%d\n", query(dfn[u]));
}
}
for (int i = ; i <= n; ++i) head[i] = bit[i] = son[i] = ;
tot = ;
}
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + ;
struct edge {
int to, id, nxt;
}edge[N*];
int n, q, s, u, v, w[N], a[N], aa[N], op;
int head[N], tot = ;
int fa[N], sz[N], dp[N], son[N], dfn[N], top[N], to[N], cnt = ;
int tree[N<<];
void add(int u, int v, int id) {
edge[tot].to =v;
edge[tot].id = id;
edge[tot].nxt = head[u];
head[u] = tot++;
}
void dfs1(int u, int o) {
dp[u] = dp[o] + ;
fa[u] = o;
sz[u] = ;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
int id = edge[i].id;
if(v != o) {
a[v] = w[id];
aa[id] = v;
dfs1(v, u);
sz[u] += sz[v];
if(sz[son[u]] < sz[v]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
to[cnt] = u;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
void push_up(int rt) {
tree[rt] = tree[rt<<] + tree[rt<<|];
}
void update(int p, int v, int rt, int l, int r) {
if(l == r) {
tree[rt] += v;
return ;
}
int m = l+r >> ;
if(p <= m) update(p, v, ls);
else update(p, v, rs);
push_up(rt);
}
int query(int L, int R, int rt, int l, int r) {
if(L > R) return ;
if(L <= l && r <= R) return tree[rt];
int m = l+r >> , ans = ;
if(L <= m) ans += query(L, R, ls);
if(R > m) ans += query(L, R, rs);
return ans;
}
void build(int rt, int l, int r) {
if(l == r) {
tree[rt] = a[to[l]];
return ;
}
int m = l+r >> ;
build(ls);
build(rs);
push_up(rt);
}
int sum(int u, int v) {
int ans = , fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] < dp[fv]) swap(u, v), swap(fu, fv);
ans += query(dfn[fu], dfn[u], , , n);
u = fa[fu];
fu = top[u];
}
if(dfn[u] <= dfn[v]) ans += query(dfn[u]+, dfn[v], , , n);
else ans += query(dfn[v]+, dfn[u], , , n);
return ans;
}
int main() {
scanf("%d %d %d", &n, &q, &s);
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w[i]), add(u, v, i), add(v, u, i);
dfs1(, );
dfs2(, );
build(, , n);
while(q--) {
scanf("%d", &op);
if(op == ) {
scanf("%d", &u);
printf("%d\n", sum(s, u));
s = u;
}
else {
scanf("%d %d", &u, &v);
update(dfn[aa[u]], v-a[aa[u]], , , n);
a[aa[u]] = v;
}
}
return ;
}
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<iostream>
#include<cstdio>
#include<vector>
#include<climits>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e4 + ;
vector<pii> g[N];
int T, n, u, v, w[N], a[N], aa[N];
char s[];
int fa[N], sz[N], dp[N], son[N], dfn[N], top[N], to[N], cnt = ;
struct node {
int mx, mn, lazy;
}tree[N<<];
void dfs1(int u, int o) {
fa[u] = o;
dp[u] = dp[o] + ;
sz[u] = ;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int id = g[u][i].se;
if(v != o) {
dfs1(v, u);
sz[u] += sz[v];
a[v] = w[id];
aa[id] = v;
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
to[cnt] = u;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
void push_up(int rt) {
tree[rt].mn = min(tree[rt<<].mn, tree[rt<<|].mn);
tree[rt].mx = max(tree[rt<<].mx, tree[rt<<|].mx);
}
void push_down(int rt) {
tree[rt<<].mn = -tree[rt<<].mn;
tree[rt<<].mx = -tree[rt<<].mx;
tree[rt<<|].mn = -tree[rt<<|].mn;
tree[rt<<|].mx = -tree[rt<<|].mx;
swap(tree[rt<<].mn, tree[rt<<].mx);
swap(tree[rt<<|].mn, tree[rt<<|].mx);
tree[rt<<].lazy ^= ;
tree[rt<<|].lazy ^= ;
tree[rt].lazy = ;
}
void build(int rt, int l, int r) {
tree[rt].lazy = ;
if(l == r) {
tree[rt].mn = tree[rt].mx = a[to[l]];
return ;
}
int m = l+r >> ;
build(ls);
build(rs);
push_up(rt);
}
void update(int p, int v, int rt, int l, int r) {
if(l == r) {
tree[rt].mn = tree[rt].mx = v;
return ;
}
if(tree[rt].lazy) push_down(rt);
int m = l+r >> ;
if(p <= m) update(p, v, ls);
else update(p, v, rs);
push_up(rt);
}
void Update(int L, int R, int rt, int l, int r) {
if(L > R) return ;
if(L <= l && r <= R) {
tree[rt].lazy ^= ;
tree[rt].mx = -tree[rt].mx;
tree[rt].mn = -tree[rt].mn;
swap(tree[rt].mx, tree[rt].mn);
return ;
}
if(tree[rt].lazy) push_down(rt);
int m = l+r >> ;
if(L <= m) Update(L, R, ls);
if(R > m) Update(L, R, rs);
push_up(rt);
}
int query(int L, int R, int rt, int l, int r) {
if(L > R) return INT_MIN;
if(L <= l && r <= R) return tree[rt].mx;
if(tree[rt].lazy) push_down(rt);
int m = l+r >> , ans = INT_MIN;
if(L <= m) ans = max(ans, query(L, R, ls));
if(R > m) ans = max(ans, query(L, R, rs));
push_up(rt);
return ans;
}
void change(int u, int v) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] < dp[fv]) swap(u, v), swap(fu, fv);
Update(dfn[fu], dfn[u], , , n);
u = fa[fu];
fu = top[u];
}
if(dfn[u] <= dfn[v]) Update(dfn[u]+, dfn[v], , , n);
else Update(dfn[v]+, dfn[u], , , n);
}
int solve(int u , int v) {
int ans = INT_MIN, fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] < dp[fv]) swap(u, v), swap(fu, fv);
ans = max(ans, query(dfn[fu], dfn[u], , , n));
u = fa[fu];
fu = top[u];
}
if(dfn[u] <= dfn[v]) ans = max(ans, query(dfn[u]+, dfn[v], , , n));
else ans = max(ans, query(dfn[v]+, dfn[u], , , n));
return ans;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = ; i < n; ++i) scanf("%d %d %d", &u, &v, &w[i]), g[u].pb(mp(v, i)), g[v].pb(mp(u, i));
dp[] = ;
dfs1(, );
dfs2(, );
build(, , n);
while(true) {
scanf("%s", s);
if(s[] == 'D') break;
scanf("%d %d", &u, &v);
if(s[] == 'C') {
update(dfn[aa[u]], v, , , n);
}
else if(s[] == 'N') {
change(u, v);
}
else {
printf("%d\n", solve(u, v));
}
}
cnt = ;
for (int i = ; i <= n; ++i) g[i].clear(), son[i] = ;
}
return ;
}
最新文章
- xampp 端口冲突
- CF453C Little Pony and Summer Sun Celebration （DFS）
- HDU2845 DP
- js中的什么时候需要用new来实例化?
- Python Import 详解
- python+Eclipse+pydev环境搭建(转)
- JNIEnv解析
- 几个RTP的开源实现
- ubuntu首次给root用户设置密码
- 345. Reverse Vowels of a String（C++）
- [R] /usr/share/doc/apache2/README.Debian.gz
- [转] Nginx + CGI/FastCGI + C/Cpp
- JMeter使用代理录制脚本
- 微信小程序 服务器端生成用户登陆环节的 3rd_session
- Sticks Problem
- 使用RedisDesktopManager工具，解决连接失败问题
- Java如何获取URL的部分？
- oracle vm突然黑屏了
- pycharm破解补丁的使用
- 浅谈Matcher和pattern的使用