Pipipapi

4772

-Acwing-

ding-zk
tryflow

acwing_zfw
AcWing_Umbrella

konkayy
qujunyi

moreexcellent
Aurora丶
QL_GI

Pipipapi
12小时前

### 题目描述

#### 样例

Sample Input 1
3
1 2
2 3
Sample Output 1
3
2
3

Sample Input 2
2
1 2
Sample Output 2
1
1

Sample Input 3
6
1 6
1 5
1 3
1 4
1 2
Sample Output 3
5
9
9
9
9
9


### 算法:推公式加dfs求解

##### O(n)

$$dist[s]=dist[j]+n-s*son[s]$$

1.做一遍深搜搜出dist[1]，并且记录以1为根的树的所有结点的儿子结点个数
2.再做一遍深搜，按照由近到远的顺序，先求儿子结点的答案，再递归求儿子的儿子的答案即可

#### C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define N 200010
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
//=================================

int n;
int e[2*N],ne[2*N],h[N],idx=0;
long long son[N],dist[N];

void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int pre,int len){
dist[1]+=len;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==pre) continue;
dfs(j,u,len+1);
son[u]+=son[j];
}
}

void dfs(int u,int pre){
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==pre) continue;
dist[j]=dist[u]+n-2ll*son[j];
dfs(j,u);
}
}

//=================================
int main(){
memset(h,-1,sizeof h);
scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
}
for(int i=1;i<=n;i++) son[i]=1;
dfs(1,-1,0);

dfs(1,-1);

for(int i=1;i<=n;i++)
printf("%lld\n",dist[i]);

return 0;
}


Pipipapi
20小时前
#include<bits/stdc++.h>
using namespace std;
const int M = 210;
const int N = 1010;

int n,T,m;
int f[N][N];
int a[N],t[N],sub[N],s[N],sum[N][N];

int main(){
cin >> n;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=n;i++)
cin >> sub[i];
for(int j=2;j<=n;j++)
cin >> t[j];
for(int i=2;i<=n;i++)
s[i]+=s[i-1]+t[i];
cin >> m;

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]=sum[i][j-1]+max(0,a[i]-(j-1)*sub[i]);

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j-t[i]];
if(j>=s[i])
for(int k=s[i-1];k<=j-t[i];k++){
int tt=j-k-t[i];
f[i][j]=max(f[i][j],f[i-1][k]+sum[i][tt]);
}
}

int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,f[i][m]);
cout << ans << endl;
}


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010

int lf[N],rt[N],q[N],st[N],hh=0,f[N];
int n;

signed main(){
while(scanf("%lld",&n),n){
for(int i=1;i<=n;i++)
scanf("%lld",&q[i]);
q[0]=q[n+1]=-1;

hh=-1;
st[++hh]=0;
for(int i=1;i<=n;i++){
while(q[st[hh]]>=q[i]) hh--;
lf[i]=i-st[hh];
st[++hh]=i;
}

hh=-1;
st[++hh]=n+1;
for(int i=n;i;i--){
while(q[st[hh]]>=q[i]) hh--;
rt[i]=st[hh]-i;
st[++hh]=i;
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,q[i]*(rt[i]+lf[i]-1));
printf("%lld\n",ans);
}
return 0;
}


#include<bits/stdc++.h>

using namespace std;

#define N 100010

int n,d[N];
int e[2*N],ne[2*N],h[N],idx=0;
int ans=0;

void add(int a,int b){
e[idx]=b;
ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u,int pre){
int res=1,son=0;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==pre) continue;

son=dfs(j,u);
if(son%2==0) ans++;
res+=son;
}
return res;
}

int main(){
memset(h,-1,sizeof h);

scanf("%d",&n);
if(n&1){puts("-1");return 0;}
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
d[a]++,d[b]++;
}
dfs(1,-1);
cout << ans << endl;
return 0;
}


class Solution {
public:
bool find132pattern(vector<int>& nums) {
stack<int> S;
int second_big=-0x3f3f3f3f;

if(nums.size()<3) return false;

for(int i=nums.size()-1;i>=0;i--){

if(nums[i]<second_big) return true;
while(S.size()&&nums[i]>S.top()){
second_big=S.top();
S.pop();
}
S.push(nums[i]);
}

return false;
}
};


#include<bits/stdc++.h>
using namespace std;

#define N 100010

const int M = 35;

int n,m,root;
int mid_ord[M],back_ord[M];
unordered_map<int,int> pos,l,r;

int build(int ml,int mr,int bl,int br){  //返回当前树的根
int u=back_ord[br];
int k=pos[u]; //找到根节点的位置
if(ml<k) l[u] = build(ml,k-1,bl,bl+k-1-ml);
if(mr>k) r[u] = build(k+1,mr,bl+k-ml,br-1);
return u;
}

void bfs(int root){
queue<int> Q;
Q.push(root);

while(Q.size()){
auto u =Q.front();
Q.pop();

cout << u << " " ;

if(l.count(u)){
Q.push(l[u]);
}
if(r.count(u)){
Q.push(r[u]);
}
}
}

int main(){
cin >> n;
for(int i=1;i<=n;i++)
cin >> back_ord[i];

for(int i=1;i<=n;i++){
cin >> mid_ord[i];
pos[mid_ord[i]]=i;
}

root=build(1,n,1,n);
bfs(root);

return 0;
}


dfs

/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
*   public:
*     // Return true if this NestedInteger holds a single integer, rather than a nested list.
*     bool isInteger() const;
*
*     // Return the single integer that this NestedInteger holds, if it holds a single integer
*     // The result is undefined if this NestedInteger holds a nested list
*     int getInteger() const;
*
*     // Return the nested list that this NestedInteger holds, if it holds a nested list
*     // The result is undefined if this NestedInteger holds a single integer
*     const vector<NestedInteger> &getList() const;
* };
*/

class NestedIterator {
public:
vector<int> q;
int k=0;

NestedIterator(vector<NestedInteger> &nestedList) {
k = 0;
for(auto &l:nestedList){
dfs(l);
}
}

void dfs(NestedInteger& l){
if(l.isInteger()) q.push_back(l.getInteger());
else{
for(auto& j:l.getList())
dfs(j);
}
}

int next() {
return q[k++];
}

bool hasNext() {
return k < q.size();
}
};

/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i(nestedList);
* while (i.hasNext()) cout << i.next();
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N =16;

//状态1表示扩张，0表示收缩
int f[N][226][N][N][2][2],a[N][N],b[N][N],n,m,t,i,j,k,l,r,x,y,p,q,ans,now,ai,al,ar,ax,ay;
char cl[N][226][N][N][2][2],cr[N][226][N][N][2][2],dx[N][226][N][N][2][2],dy[N][226][N][N][2][2];

inline void update(int dat,int L,int R,int X,int Y){ //传入权值之和，左边界、右边界列号，左边界轮廓状态，右边界轮廓状态
if(dat<f[i][j][l][r][x][y]) return ;
f[i][j][l][r][x][y]=dat;
//记录方案，分别是左边右边
cl[i][j][l][r][x][y]=L,cr[i][j][l][r][x][y]=R; //分别记录上一层转移的左边界、右边界
dx[i][j][l][r][x][y]=X,dy[i][j][l][r][x][y]=Y; //分别记录上一层转移的左边界状态。右边界状态
}

void print(int i,int j,int l,int r,int x,int y){  //递归方式记录方案
if(!j) return;
print(i-1,j-(r-l+1),cl[i][j][l][r][x][y],cr[i][j][l][r][x][y],dx[i][j][l][r][x][y],dy[i][j][l][r][x][y]);
for(j=l;j<=r;j++) printf("%d %d\n",i,j);
}

int main(){
cin >> n >> m >> t;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf("%d",&a[i][j]);
b[i][j]=b[i][j-1]+a[i][j];
}

memset(f,0xcf,sizeof f); //0xcf直接赋值成负数

for( i=1;i<=n;i++) //枚举行数
for( j=1;j<=t;j++) //枚举防止的方块数
for( l=1;l<=m;l++) //枚举左边界
for(r=l;r<=m;r++) //枚举右边界
{
if((k=r-l+1)>j) break;
now=b[i][r]-b[i][l-1];
for( x=0;x<2;x++)
for(y=0;y<2;y++)
update(now,m,0,x,y);

x=y=1; //左右扩张
for(p=l;p<=r;p++) //枚举每一行
for(q=p;q<=r;q++)
update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1); //左右都递增只能由递增的状态转移过去

x=y=0; //左右收缩
for(p=1;p<=l;p++)
for(q=r;q<=m;q++){
update(f[i-1][j-k][p][q][0][0]+now,p,q,0,0);
update(f[i-1][j-k][p][q][1][0]+now,p,q,1,0);
update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
}

x=1,y=0; //左收缩右收缩
for(p=l;p<=r;p++)
for(q=r;q<=m;q++){
update(f[i-1][j-k][p][q][1][0]+now,p,q,1,0);
update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
}

x=0,y=1;
for(p=1;p<=l;p++)
for(q=l;q<=r;q++){
update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
}
}

for(i=1;i<=n;i++)
for(l=1;l<=m;l++)
for(r=l;r<=m;r++)
for(x=0;x<2;x++)
for(y=0;y<2;y++)
if(f[i][t][l][r][x][y]>ans){
ans=f[i][t][l][r][x][y];
ai=i,al=l,ar=r,ax=x,ay=y;
}

cout << "Oil : " << ans << endl;
print(ai,t,al,ar,ax,ay);

return 0;
}



#include<bits/stdc++.h>
using namespace std;
#define N 20010
#define M 100010

int n,m;
int fa[N],oppo[N];
struct Edge{
int a,b,v;
bool operator<(const Edge &W){
return W.v < v;
}
}edge[M];

int find(int x){
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}

void join(int a,int b){
a=find(a),b=find(b);
if(a!=b){
fa[a]=b;
}
}

int main(){
scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)
fa[i]=i;

for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].v);

sort(edge+1,edge+1+m);

for(int i=1;i<=m+1;i++){
int a=edge[i].a,b=edge[i].b,v=edge[i].v;
int pa=find(a),pb=find(b);
if(pa==pb){
printf("%d\n",v);
exit(0);
}
else{
if(!oppo[a]) oppo[a]=b;
else join(oppo[a],b);
if(!oppo[b]) oppo[b]=a;
else join(oppo[b],a);
}
}

puts("0");

return 0;
}


#include<bits/stdc++.h>
using namespace std;
#define N 1000010

int a[N],d[N],s[N],t[N],diff[N];
int n,m;

inline bool check(int x){
memset(diff,0,sizeof diff);
for(int i=1;i<=x;i++)
diff[s[i]]+=d[i],diff[t[i]+1]-=d[i];
int need=0;
for(int i=1;i<=n;i++){
need+=diff[i];
if(a[i]<need) return false;
}
return true;
}

int main(){
scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)
scanf("%d",&a[i]);

for(int i=1;i<=m;i++){
scanf("%d%d%d",&d[i],&s[i],&t[i]);
}

if(check(m)){
puts("0");
return 0;
}
int l=1,r=m;
while(l<r){
int mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
puts("-1");
printf("%d\n",l);
return 0;
}